3.6 VCG: The Myerson-Satterthwaite Theorem

Loading...

En provenance du cours de Stanford University

Game Theory II: Advanced Applications

307 notes

Stanford University

Game Theory II: Advanced Applications

307 notes

Popularized by movies such as "A Beautiful Mind", game theory is the mathematical modeling of strategic interaction among rational (and irrational) agents. Over four weeks of lectures, this advanced course considers how to design interactions between agents in order to achieve good social outcomes. Three main topics are covered: social choice theory (i.e., collective decision making and voting systems), mechanism design, and auctions. In the first week we consider the problem of aggregating different agents' preferences, discussing voting rules and the challenges faced in collective decision making. We present some of the most important theoretical results in the area: notably, Arrow's Theorem, which proves that there is no "perfect" voting system, and also the Gibbard-Satterthwaite and Muller-Satterthwaite Theorems. We move on to consider the problem of making collective decisions when agents are self interested and can strategically misreport their preferences. We explain "mechanism design" -- a broad framework for designing interactions between self-interested agents -- and give some key theoretical results. Our third week focuses on the problem of designing mechanisms to maximize aggregate happiness across agents, and presents the powerful family of Vickrey-Clarke-Groves mechanisms. The course wraps up with a fourth week that considers the problem of allocating scarce resources among self-interested agents, and that provides an introduction to auction theory. You can find a full syllabus and description of the course here: http://web.stanford.edu/~jacksonm/GTOC-II-Syllabus.html There is also a predecessor course to this one, for those who want to learn or remind themselves of the basic concepts of game theory: https://www.coursera.org/learn/game-theory-1 An intro video can be found here: http://web.stanford.edu/~jacksonm/Game-Theory-2-Intro.mp4

À partir de la leçon

Efficient Mechanisms

The description goes here

3.1 VCG: Taste 10:20

3.2 VCG: Definitions 18:20

3.3 VCG: Examples 7:11

3.4 VCG: Limitations 11:22

3.5 VCG: Individual Rationality and Budget Balance in VCG 16:09

3.6 VCG: The Myerson-Satterthwaite Theorem 19:29

Rencontrer les enseignants

Matthew O. Jackson
Professor
Economics
Kevin Leyton-Brown
Professor
Computer Science
Yoav Shoham
Professor
Computer Science

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?

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.

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,

we can think of listing buyer's value first, then seller's value.

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.

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.

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.

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

When the buyer's value is .1 we're not getting a trade.

Okay.

So, there's were the inefficiency is.

Sometimes, the buyer has a higher value than the seller, and

we're not getting trade.

So that's the basic inefficiency.

So, we're better off to set the high price in terms of the seller.

And we get inefficient trade.

These don't trade, even though they should.

Okay.

What about other mechanisms?

Well, let's suppose,

that we sort of forced the seller to somehow charge a lower price.

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.

There are some situations where you could get efficient trade.

And let me just go through one to make clear what's going on here.

Supposed that we're in situation where the buyer's value is always above some

value B, and the seller's value is always below that.

So there is some level v.

And we know that buyers always value these cars more.

And sellers always value the cars less.

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.

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.

So here the payment conditional on high valued buyer and high

valued seller is at least 0.9, otherwise the seller doesn't want to sell it.

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.

So now what we need to do is, we've got individual rationality satisfied for

three of the prices.

We want to make sure we're going to get an individual rationality here.

Well, that's going to be easy.

Any price between 0 and 1 will be individually rational.

The difficulty is going to be to get the incentive compatibility condition to hold.

Okay? So now we want to check what's going to be

true so that the people want to tell us what their actual values are.

Okay? So instead of compatibility for

the seller of type 0, not wanting to pretend to be a 0.9 type.

Let's go through that.

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

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.

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.

And this is really impossible to get around, and one thing to emphasize here

and this is sot of the power of the revelation theorem.

Think of any mechanism you would want.

Right. Think of any mechanism.

If that mechanism somehow has equilibrium that will lead to efficient trade,

we can right that mechanism as a direct mechanism.

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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play