0:00

Hi folks.

Â So this is Matt again.

Â And we are now going to talk about Vickrey-Clarke-Groves Mechanisms,

Â or VCG mechanisms.

Â And these have become one of the most well studied set of mechanisms in game theory.

Â And with good reason,

Â they have wonderful properties, some very interesting properties.

Â And let's talk a little bit about the kinds of positive results we'll get now

Â out of these mechanisms before we're going to the detailed definitions and so forth.

Â So, we're going to work in a quasilinear setting, and we're going to work here.

Â Remember now,

Â we'll look at direction mechanisms where you society will have a choice rule and

Â the payment rule based on what preferences people report to the mechanism.

Â And the nice thing about VCG mechanisms, Vickrey-Clarke-Groves mechanisms,

Â is that they will have truth as a dominant strategy.

Â So people won't have to worry about other individuals are doing

Â regardless of what their preferences are, the best thing they can do in terms of

Â maximizing their utility is to tell the truth.

Â And, this mechanism is also going to choose efficient x's.

Â So choices here mean when we choose, when we think about which x in X maximizes

Â the overall total sum of utilities in a society, it's going to pick those.

Â So, it might not be efficient in terms of making all the payments balance.

Â But it's going to make efficient choices, okay.

Â Now, these mechanisms in terms of the history of this,

Â Vickrey was the first to define these in an auction settings.

Â So this is going to have a close relationship to second price auctions and

Â basically, generalizes second price auctions to a more

Â general class of auctions known as Vickrey auctions in the auction setting.

Â 1:46

Clarke then generalize that to

Â a more general class of settings and define what was known as

Â the pivotal mechanism which is a special class of these mechanisms.

Â And then Groves gave basically the class of all such mechanisms and

Â there are some nice properties of a more general class of these.

Â And so we'll look at these in more detail.

Â The nice thing is we're going to have dominant strategies and

Â efficient choices, and

Â the quasilinearity is going to be critical here in making sure everything works.

Â And so we're looking at private values, so conditional utility independence

Â in general, and we'll be looking at settings where we have

Â 2:33

quasilinearity is going to make things go for us, okay.

Â Under you know, some particular settings will be able to get additional things like

Â a weak budget balance condition, interim individual rationality,

Â other kinds of nice things coming out but basically,

Â the key ingredients here are going to be dominant strategies and efficiencies.

Â Okay, so let's start with the general class of these mechanisms which are known

Â as Groves mechanisms after Ted Groves.

Â And so we're looking at direct mechanisms so

Â this is going to be making a choice out of whatever our x set is.

Â And then the ps are going to be, the p is going to be in our n again.

Â So it's telling a payment for each of the individuals.

Â And the interesting thing about a Groves mechanism is a Groves

Â mechanism's going to be any mechanism of the following sort.

Â Look at the announced utility functions.

Â Each person is telling us now what's their evaluation function.

Â That's their private information, so we get these announcements.

Â So people are telling us v hat 1 through v hat n

Â which are telling us how do they value the different x alternatives.

Â So, society first of all is going to make a choice

Â which maximizes the total sum of those.

Â If that's unique, then that ties this thing down exactly.

Â Sometimes there could be ties.

Â It's going to always pick something which is best for

Â society in terms of overall maximization.

Â Then the key thing here is going to be the payment rule.

Â And what's the payment rule going to look like?

Â The payment rule for a given individual is going to be something which is

Â 4:26

utility functions announced by the other individuals other than i.

Â And, it's also going to have a part here.

Â We'll subtract off the sum of the announced

Â valuation functions evaluated at the chosen alternative by society.

Â Okay, so society makes a choice, we look at how much does everyone else,

Â in terms of utility for that.

Â We can add in some other thing that doesn't depend on a given individual.

Â So sometimes it's going to be useful to add in other things, and

Â we'll talk about that in a moment.

Â Anything which has this structure to it is known as a Groves mechanism.

Â Okay, so this is a particular class of mechanisms.

Â Sometimes these are referred to as VCG mechanisms.

Â 5:25

Okay, so now let's look at Vickrey-Clerke-Groves mechanisms of

Â the special class which is also this go by different names and different literatures

Â on the economics that are sure this was originally known as a pivotal mechanism.

Â In part of the computer science literature and the game theory literature more

Â generally is becoming known Vickery or VCG mechanism.

Â Sometimes VCG is used to look at the broader class but

Â what's specialized here is, if you remember that h function we had.

Â So we had an h function, hi(v hat-i).

Â That function now takes a very specific form.

Â And that specific form, in particular, is one where what

Â we do is pick something which maximizes the sum of everyone else's utility.

Â So what would society choose if i were ignored?

Â 6:19

And then look at the total sum of utilities that would come out of that.

Â And compare that to what people get when i is taken into account, right?

Â So this is the choice that's made when i is being accounted for.

Â This is the choice that would be made if we ignored i and this pivotal mechanism.

Â What it does in terms of i's payment is say,

Â how much would everyone get if we ignored you?

Â How much does everyone else get if we take you into account?

Â This is generally going to be a lower number, right?

Â This is going to have to be a lower number.

Â People can't be made better off by including i in terms of the decision.

Â That all they can do is distort things away from the overall maximizer for

Â these individuals.

Â So this number is generally going to be a non-negative number.

Â So this will be a payment that different individuals would be making

Â into the society.

Â Okay, so let's have a look at what we end up with here.

Â And so we've got this structure.

Â Something which maximizes overall utility, and that particular payment scheme.

Â And so what you get paid is,

Â everyone's utility under the allocation is actually chosen, except your own.

Â You get that as the direct utility.

Â And then you get charged everybody's utility so when we take off this minus pi,

Â what you're going to be charged is how much everyone else would've gotten in

Â this world where they didn't have to take you into account.

Â Less what they're getting in a world where they do have to take you into account.

Â And so we can think of this as the social cost of an individual i.

Â Right, so this is social cost, Of i.

Â What does that mean?

Â That means having i present imposes some change in utility for

Â the other individuals.

Â Individuals are paying their social cost.

Â 8:24

Who pays 0 in this world?

Â Well, people who end up not affecting the outcome at all.

Â So, their presence or non presence,

Â their announcement of their utility function didn't affect things over all.

Â So, who pays more than 0?

Â Pivotal agents who make things worse by existing.

Â 8:44

So there's situations where the fact that they existed

Â actually changed the outcome in a way that made the individuals worse off.

Â Who winds up getting paid?

Â Well people can, in some circumstances under some of these mechanisms gets paid

Â by making things better off for other individuals.

Â 9:02

Okay, one nice thing about these mechanisms and the beauty

Â of these mechanisms is that truth telling's going to be a dominant strategy

Â under any Groves mechanism, including the pivotal mechanism or these VCG mechanisms.

Â So, when we have this basic form

Â the theorem tells us that truth is the dominant strategy.

Â And let's go through that.

Â So we'll first go through this theorem, and

Â then we'll talk about a converse theorem that says basically, if you want truth to

Â be a dominant strategy in these settings with quasilinear preferences and

Â private values, it's going to have to be a Grove mechanism.

Â So these mechanisms will be dominant strategy.

Â And basically in this setting they be the only dominant strategy mechanisms.

Â That results in efficient x choices.

Â Okay, so let's have a look at this, so let's look at it to try and

Â see why this theorem is true.

Â Let's think of what i's problem is.

Â So what they're getting is they're getting this is their true utility vi.

Â And they're thinking about what they should announce, right?

Â So, i is choosing, what function should I tell the mechanism

Â that I have in terms of like, my utility function.

Â So, that's going to affects the outcome, and it's going to affect the price.

Â And this is the overall utility,

Â so they want to choose the announcement to maximize the utility function.

Â So let's have a look at the Groves mechanism.

Â Substitute in for this and then see what people's incentives are in the world.

Â So under a Groves mechanism your payment were looks like this.

Â So it looks like an hi minus the v hat and

Â then we take the minus of the over all thing and we end up with this.

Â 11:00

So first of all, notice that this thing does not depend on v hat i, so

Â maximizing that is equivalent to maximizing this when we ignore it.

Â So now we've boiled this problem down to solving this problem.

Â So maximize vi of the chosen alternative

Â as a function of what you announce plus the other people's announced utilities.

Â Now one thing to notice, is this begins to look like you're just trying to maximize

Â the overall sum of utilities where yours is the truthful and

Â then everyone else is what the announced one is.

Â So I would like to choose a declaration which would lead

Â the mechanism to pick an outcome which is going to maximize this overall thing.

Â 11:46

So what you'd like to do is choose a v head i that will

Â lead the mechanism to make a choice which solves this problem.

Â So if we go back and look at this problem maximizing overall the v head i is

Â equivalent to saying let's try and get the mechanism to choose an x

Â which will maximize this overall if that declaration gets an x that maximizes this.

Â Then it's certainly doing it as well as possible.

Â 12:14

Now remember under a Groves mechanism,

Â the x of the v hat i is something which maximizes

Â exactly the sum where what you've done is put in your announced utility.

Â If you want to get them to do it with respect to your true utility then

Â the way in which to do this is to have your announced utility be equal to

Â your true utility and then they'll be maximizing exactly the function that you

Â want them to be maximizing and so that means that truth is a dominant strategy.

Â So the Groves mechanism will choose x in a way that solves this maximization problem

Â precisely when v hat is equal to vi.

Â Therefore, truth is a dominant strategy.

Â So this is a deceivingly simple proof, so

Â it takes a while to go back through this, convince yourself it's true, but

Â the basic idea here is that the payment that a given individual has

Â is essentially what everyone else's announced utility function is.

Â And whether those are truthful or

Â not, from their perspective, what they're getting in terms of an outcome

Â is something which then maximizes the overall total sum of utilities.

Â Because what they're doing is maximizing their true utility, plus what other people

Â have told the mechanism their utility functions look like, and

Â by being truthful they get an outcome which maximizes that overall total sum.

Â Which indeed is the best they can do,

Â in terms of maximizing their utility given this payment rule.

Â So the nice thing about these VCG mechanisms, or in general, the Groves

Â mechanism, is they align the individuals' incentives with the society's incentives,

Â by making sure that the payment rule accounts for what their decision choice

Â is what the impact of their announcement is on everyone elses utility.

Â Okay, now the uniqueness of these things in terms of being the converse theorem.

Â There's a theorem by Green and Laffont from the late 1970s or

Â early 80s which then says there's a converse here.

Â So suppose that for any utility function,

Â 15:10

That's going to have truthful recording as a dominant strategy for all agents and

Â preferences only if it's a Groves mechanism.

Â So the payment rule has to look like what we said in terms of Groves mechanism.

Â That's the only way that you can be truthful for

Â all possible announcements of preferences.

Â So, not only are the Groves mechanisms dominant strategy incentive compatible,

Â but if we require efficient outcomes, these are the only ones that work.

Â Okay, so I won't prove this explicitly.

Â The proof is actually fairly straightforward.

Â You can find the version in a survey I wrote on mechanism design on my website.

Â But in terms of summary here so far, what have we got?

Â Groves mechanisms and a special class of those, the pivotal mechanisms or

Â VCG mechanisms, have really nice properties in terms of incentives.

Â Truth is always a dominant strategy.

Â The agent's payment rules, they basically align their incentives

Â with this society in terms of making sure that they're taking into account their

Â impact on other individuals' preferences and utilities and

Â therefore we end up with efficient outcome choices.

Â So that leads people to internalize the externalities and

Â leads to efficient choices over the x's.

Â 16:36

Now one thing that is also important to emphasize is that it might

Â be that these mechanisms are not overall efficient in

Â the sense that we might have to charge the agents money in order to get this to work.

Â So it could be that the sum of the payments that pi's is greater than 0.

Â So that means that people are making a bunch of payments into the society and

Â we're not giving them all back to the society.

Â So either we have to funnel them off to somebody who's not involved in any of

Â the decision process, or we're going to have to burn that.

Â If we try and give it back,

Â that could change the incentives that we've just aligned so nicely.

Â So the part of the issue about this is we've put these payment rules in,

Â which align incentives very nicely.

Â But in order to do that, we might have to be charging agents

Â a lot in terms of what their impact on the society is.

Â And in order to get things to balance,

Â we might have to give up some nice conditions that we'd want.

Â So nice thing about these mechanisms, dominant strategies and

Â that's why they've been studied so extensively.

Â There's a number of settings where they form nice benchmarks and

Â have really a long list of nice properties.

Â There are other settings where they've serve as a benchmark, and

Â don't satisfy all the conditions we'd want, and

Â that generally has to do with the balance kind of conditions with the payments.

Â And the idea that sometimes people will be charged even if they would

Â rather not participate in the mechanisms, so we might want to think about individual

Â rationality conditions, balance conditions, and other kinds of things.

Â So we'll take a look at these in more detail and context, and

Â that'll be our next thing up.

Â