0:00

Okay, so, we're back again.

Â And we're going to talk a little bit

Â about what's known as the Myerson-Satterthwaite Theorem.

Â So Mark Satterthwaite, you've seen his name on several different theorems now,

Â the Muller-Satterthwaite, Gibberd-Satterthwaite, and

Â now the Myerson-Satterthwaite Theorem.

Â And what this theorem refers to is trade

Â And it's basically going to say that it's going to be difficult to get efficient

Â trade out with volunteering participation.

Â And when we talked about strikes and so forth, at the beginning

Â of last week One thing that's going to be important in understanding

Â why we might have difficulties getting trade out is that people can have

Â private information about their utilities for various exchange of goods.

Â So how much am I willing to work?

Â How much do I value a job?

Â 0:54

Can we design a mechanism that always results in efficient trade?

Â Are strikes unavoidable?

Â That's the basic essence here.

Â And the conclusions that we're going to find out of this result are going to be

Â that if it's not always completely obvious that a trade should be taking place,

Â then it's going to be impossible to align incentives to get efficient trades out,

Â even in a incentive compatible way.

Â And so we look at the very very simple trade setting and

Â even in that simple trade setting, we're going to see that there's going to be

Â difficulties in getting efficient trade out.

Â And that is really a very important and

Â fundamental result that comes out of game theory and mechanism design.

Â In terms of understanding, why it is that we're going to have

Â breakdown in bargaining, why it is that we don't always get efficient outcomes.

Â This is really a fundamental insight and it came out of this area.

Â Okay, so it'll be a fairly easy one to see too.

Â So, we're going to look at an exchange of a simple,

Â a single unit of an indivisible good.

Â Okay, so just, I've got something,

Â I've got a car I want to sell it, and I know how much it's worth to me,

Â you know how much it's worth to you, and we start haggling.

Â Okay, so we're going to haggle over this, and in particular,

Â let's think of the seller, the seller has some value in [0,1].

Â So we're just going to normalize things to lie in the unit interval.

Â But, think of this as saying that the seller's value of this car.

Â They're not going to give it away for nothing.

Â They have some value for it,

Â how much is it really worth before they're going to be willing to part.

Â The buyer shows up.

Â They buyer has some value for the car as well.

Â Theta b.

Â And generally, we're going to think of this as sometimes the buyers

Â going to have a higher value than the seller.

Â Sometimes, they might not.

Â Sometimes, the buyer might think that the car's not worth as much as the seller

Â thinks it's worth.

Â And therefore, it won't be efficient to trade.

Â And so, we're in a setting where we've got these two different evaluations and

Â now they search going through some mechanism, haggling, and

Â we want to see what the outcome looks like.

Â Let's do a very simple example, which will be useful in illustrating and

Â actually proving the main theorem here.

Â 3:04

So let's think of a situation where the buyer's value can either be very low .1 Or

Â high at 1, and the seller can either think this thing is worthless

Â at a value of 0 or they're really attached to it at .9.

Â So we got these two values for the buyer, and two values for the seller,

Â and what's true is if we look at different combinations, they could have, basically,

Â in all cases except one, the buyer's value is higher than the seller's value.

Â So in three out of the four cases that are possible in these combinations,

Â 3:47

You could have 0.1, 0 We could have .1, .9.

Â We could have 1, 0, or 1.9.

Â So those are the four combinations And

Â basically, in three of these, the buyers value is higher than the sellers, and

Â we should have a transaction, because now there's

Â an efficiency gain in trading the good from the seller to the buyer.

Â We get a higher utility, they can make a payment.

Â There's gains from trade here, okay.

Â The only case where there shouldn't be trade, is this case,

Â where the buyer ends up having a lower value, thinks it's not worth very much.

Â The seller thinks it's worth a lot.

Â In that case, it's better to leave it in the sellers hands.

Â It's more valuable to the seller than the buyer.

Â Okay, that's the setting.

Â 4:36

And let's think of a mechanism here.

Â So, let's suppose that the seller gets to name any price.

Â Okay, so this a simple take it or leave it offer.

Â So, the seller just puts out a price and says, here's my advertised price.

Â I'm not going to listen to anything, you either say yes or no at this price, okay?

Â And the buyer either buys or not at that price.

Â So, let's think of this world.

Â And in this case, let's think of the seller basically

Â should either sell at a price of .1 or 1.

Â When selling at a price of .5 doesn't make sense if you are the seller.

Â You could still charge .6 and the high-value buyer would still

Â want to buy it at .6 rather than a .5 ,and the low-value buyer isn't going to want to

Â buy at either of those So, once you go above .1 you might as well push

Â the price all the way up to 1 And you don't want to sit down near zero,

Â you might as well push it all the way up to point one, okay?

Â So, we'll presume that the buyer says yes, when in-different, but modulates and

Â epsilons basically that the seller should be saying a price

Â that either pushes up to the point one or all the way up to one, okay?

Â And now when we think about the seller,so imagine that the seller actually

Â thinks the car is worthless.

Â But they are the only one that know's that.

Â And the buyers going to show up, and now the seller can post a price.

Â And if I

Â post a price at point one, it's a sale for sure expected utility, point one.

Â 6:04

Okay, so I charge the low price, I'm going to sell to both buyers.

Â Price of one, they sell at the high price What happens

Â now if the buyers types are equally likely?

Â I'm only going to sell to the high type, and my expected utility is,

Â I'm going to sell at a value of one When the value's high so

Â the seller's value from a transaction, in this case,

Â is going to be plus p and then minus the value of the seller which is 0.

Â So, they don't lose anything by giving it away, they get plus p.

Â So in this case,

Â they're getting a price of one probability of 1/2 they get a utility of 1/2.

Â 6:42

So what's true here is, that if you let the seller make a take it or

Â leave it offer, they should set a price at a high enough level,

Â that you're only going to get trade to the high type.

Â And so now, what we end up with is an inefficiency, right?

Â So, even though the seller's value is zero

Â 7:37

Or that the buyer said, okay, after the fact that the seller

Â sets this high price of one, the buyer comes back and says really it's too bad.

Â I was the low value buyer.

Â You really should have sold it to me.

Â I was willing to pay point one.

Â You still walk away from something like this.

Â If the seller actually sells when you tell him that story

Â Then the high value buyer might as well tell that story, right?

Â So the high value buyer's going to want to pretend to be the lower value buyer and

Â drive the price down to 0.1.

Â So the basic difficulty in getting this,

Â is if you're willing to sell at the low price of the low buyer,

Â the high price buyer can try and pretend to be the low price buyer.

Â And so, the incentive compatibility condition is going to mean it's going to

Â be very difficult to get efficient trade Always beginning the good to be sold when

Â you want it to and not have people try to pretend to be someone else.

Â So the mechanisms is not going to work if

Â we actually want to get efficient trade out.

Â Okay.

Â So what do the theory say?

Â It says that there exists distributions on the buyers and sellers valuations,

Â such as, there is not exists Any mechanism, any mechanism which is

Â going to be Bayesian incentive-compatible, which is efficient,

Â weekly budget balanced, and interim individually rational.

Â So if you want to make the decision of in this case trading always when you should

Â and not trading when you shouldn't, Making sure that its weekly budget balanced, so

Â that the amount that the buyer pays is at least the amount that the seller gets.

Â So we're not having to stick in extra money in order to make this thing work.

Â and it is interminably rational ,so individuals don't want to walk away

Â once their told their value and told what they expect to get out of this mechanism.

Â They don't want to walk away from the mechanism.

Â Okay.

Â So that's the therom, and before we go into the proof.

Â Let me say a little bit about why this first part says,

Â there exist distributions for which this is true.

Â 10:10

Well, in that world there's a simple mechanism.

Â Always exchange the good, and always exchange it at a price of v.

Â So, the buyer pays v.

Â The seller gets v.

Â That's going to be strategy-proof.

Â It's going to be individually rational, it's going to satisfy budget balance,

Â the payments add up on to zero.

Â So that's a setting, where we get all the conditions we want,

Â and it's because we know that there always should be trade and we know that

Â there's a price that is always going to please all of the buyers and

Â all of the sellers So it's not going to be that this theorem is true, regardless

Â of what distribution is going to have to be that these distributions cross over.

Â And at sometimes we want trade and sometimes we don't.

Â And we've looked at an example like that and

Â in fact, let's show the proof based on our example.

Â So buyer's value is equally likely to be 0.1 or 1.

Â Seller's value is equally likely to be zero or 0.9.

Â Trade should take place for

Â all combinations of values except 0.1, 0.9 in terms of efficient trade.

Â And so what we can do is just go through the conditions, try to satisfy them, and

Â show that we can't satisfy them in all the situations.

Â What I'm going to do is, I'm going to show the proof for full budget balance,

Â not weak budget balance.

Â That's going to make the proof a little bit easier,

Â it's going to be very easy to extend.

Â So, I will allow you to do that to the case

Â where we don't require full budget balance.

Â And so here, what we're going to have is, trade should take place for

Â all the combinations, except for when the buyer values are 0.1 and 0.9.

Â And the nice part about that, just in terms of notation, is that means that we

Â can write payments down in terms of our full budget balance, just as a single

Â price, which is the payment made by the buyer And received by the seller.

Â So we can think of some price as a function of what the buyer and

Â seller's value is.

Â This is the price paid from the buyer to the seller.

Â 12:14

In weak budget balance, now you're going to have two prices.

Â One paid by the buyer, the other received by the seller.

Â And the payment paid by the buyer ,is always going to have to be at least

Â the payment received by the seller.

Â And you'll see, for quite easily that that will bound these things so

Â that everything we say in approval works through for that case.

Â So first thing, what has to be true if in

Â the situation where the values are 1 and .9,

Â so the seller has a value of .9, buyer has a value of 1.

Â By the individual rationality of the seller, and

Â here we're using ex post individual rationality in this part of the proof.

Â It's 0.9. And again,

Â I'm going to leave it to you to extend this to an expected value of

Â the interim individual rationality condition.

Â Here I'll do the x post version.

Â Again, the extension's fairly straightforward,

Â you'll just be working with expected payments instead of actual payments.

Â 13:28

When we see a low value buyer and low value seller then

Â the price can't be more than 0.1 otherwise the buyer won't want to buy it.

Â So individual rationality means the price, in that case, has to be below 0.1.

Â When we don't have trade, so

Â when there's no trade The price exchange is going to have to be zero.

Â And that's going to have to be true because of the individual rationality

Â constraints of both the buyer and the seller.

Â The buyer's not getting anything, so it can't be more than zero.

Â And the seller is Not giving anything away,

Â so they can't be charged anything either.

Â So the price is going to have to be zero in a case where we have no trade.

Â And so, now we've got three conditions on three of the price And

Â what we want to do is fill in the fourth price.

Â 14:49

If I actually truthfully, say that I'm a type 0, what am I going to get?

Â Well half the time, I'm going to be faced with a buyer of type 1,

Â half the time, I'm faced with a buyer of type .1,

Â so my expected utility's going to be an average of those two prices,

Â and it has to be better than me pretending that I'm a .9 type.

Â So alternatively I could pretend I'm a .9 type instead and

Â these would be the price I would get okay.

Â So in that situation, we can ask and I have a no value for the goods so

Â it doesn't really matter in terms of where the good goes, so in this case, this turns

Â out to be the incentive compatibility condition let's check what that implies.

Â So by 1, 2, and 3,

Â we have bounds on how low this price can be,

Â how high this price can be, and we know exactly what this price is.

Â So we know that this one, this last one has to be 0.

Â We know that this one is, the 1.9, is at least 0.9.

Â And this one is at most .1 and so in terms of an inequality we know that this

Â overall in multiplying .2 by the 2 p(1,0) + .1 has to greater than or

Â equal to .9 + 0 so we can take what we know from 2 and

Â 3 Plug them in here in terms of bounds given that we have the inequality pointing

Â from the left to the right, and that tells us then that p(1,0) has to be at least .8.

Â Okay, so in order to make sure that the seller

Â doesn't want to pretend to have the high value when they really have the low value,

Â The price is going to have to be at least 0.8 when they have the low value and

Â the buyer has the high value.

Â Okay, do the same incentive compatibility with the buyer being a high value, not

Â wanting to pretend that they have a low value, not trying to drive the price down

Â 16:53

And basically this is going to be reverse kind of calculation of the same thing.

Â And given all the symmetry here, it's not going to be surprising.

Â You can work through the details, do exactly the same kind of calculation.

Â And what do you end up with?

Â 1, 2, and 3 now are going to apply that this price has a cap of 0.2.

Â Okay so the seller has to be getting at least the price of .8,

Â the buyer can't be seeing a price of more than .2, well it's going to be difficult

Â to find a price which is at least .8 and also no more than .2 at the same time.

Â And that's impossible.

Â 17:30

So that's the end of the proof.

Â Basically, once we put in the individual rationality conditions, then the incentive

Â compatibility conditions are going to say the price has to be pretty high to keep

Â the seller honest, and

Â the price is going to have to be very low to keep the buyer honest.

Â Can't do that at the same time.

Â No price is going to work.

Â So, incentive compatibility plus individual rationality

Â Plus having trade exactly in the right situations is going to be impossible.

Â So in terms of summary, what have we learned?

Â Private information about values necessitates some inefficiencies in

Â voluntary trade.

Â And it leads to sort of a basic tension between incentives and efficiency.

Â 18:28

And so the proof here says, no matter what's going on throughout this mechanism,

Â it's going to be impossible to write anything down that's going

Â to have the desired properties of always trading when you want to and

Â being incentive compatible.

Â People are going to tend to lie and

Â that's going to lead to some inefficient trades and things not happen.

Â When you want them to.

Â And this begins to explain this question of why do we have strikes?

Â Why do we have breakdowns?

Â Why don't we always come to an agreement?

Â And you can ask yourself, if you ever walk away from a bargain when you thought

Â that trade might really be possible.

Â So sometimes, we're going to be forced to leave things on the table and

Â that's a powerful result and understanding, this is really

Â important in understanding why some inefficiency exists in the world and

Â why we're going to have difficulties getting around them.

Â To the extent that people have private information about their willingness to do

Â something, that's going to be difficult to overcome and getting for efficiency.

Â