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
3.2 VCG: Definitions
Loading...
Avis
4.7 (361 notes)
- 5 stars271 ratings
- 4 stars76 ratings
- 3 stars11 ratings
- 2 stars2 ratings
- 1 star1 ratings
MP
Apr 16, 2017
Thank you for giving me excellent information on game theory. It is very helpful course for me. Thank you Stanford University,The University of British Columbia and Coursera.
AK
Jan 10, 2019
Brilliant mind-teaser, helps you form skills that will lead to logical thinking in strategic interplays between everyday events and even the more complex one.
À partir de la leçon
Efficient Mechanisms
The description goes here
Enseigné par
Matthew O. Jackson
Professor
Kevin Leyton-Brown
Professor
Yoav Shoham
Professor
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.
© 2019 Coursera Inc. Tous droits réservés.
