3.2 VCG: Definitions

Loading...

En provenance du cours de Stanford University

Game Theory II: Advanced Applications

293 notes

Stanford University

Game Theory II: Advanced Applications

293 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

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.

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

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

going to depend on some function of what the other individuals announced.

So minus i meaning the vector of

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.

That name has more recently been used to look at a situation with a very

specific payment rule here, and we'll talk about that in a moment.

But this is a general class of Groves mechanisms.

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?

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.

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.

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.

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.

So, and there should be an i here, subscript i.

So when we looked at that payment scheme the individual is choosing this

to maximize their overall utility.

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.

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.

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,

it's so each individual could have any possible

utility function over the public decision or the non monetary decision.

So domain is going to be rich in a very particular sense that people could have

any possible utility ordering, or utility function over this set of alternatives.

Then we'll say that a mechanism that's efficient,

so it's choosing a decision as a function of the announced preferences,

which maximizes the overall utility.

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.

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.

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