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.4 VCG: Limitations
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
So far we've heard a lot of good things about VCG.
And for good reason.
But VCG also has some important limitations that this video will
introduce you to.
The first is that VCG requires that the agents tell the mechanism
everything about their private information.
This is fine if we really believe our model that the agents had utility only for
the choice that the mechanism makes and the payments that are imposed.
But in some settings, agents might interact together repeatedly, and
telling the mechanism and publicizing something about their private
information might affect their ability to compete in future interactions.
So if that's true, the agents might prefer a mechanism in which only as much
information is disclosed as is required to actually compute the social welfare,
maximizing choice, and the VCG payments.
This is often possible, and VCG requires revealing more than that.
So in such cases, a VCG wouldn't be a good choice of mechanism.
Here's something a little bit more subtle about VCG.
It turns out to be susceptible to collusion.
So let's look at the road building game.
Here we have three agents.
We're going to choose to build the road rather than not building the road,
because we get utility of 300 for building the road, and 250 for not building it.
If we look at the agents of VCG payments, let's look for example at Agent 1.
He would be paid 100,
because in the situation where he exists, Agent 2 has happiness of 100.
And he's going to have to pay 250, because in the world where he doesn't exist,
the road won't be built, and there'll be Agent 3 will have 250 units of utility.
So, in other words, he's going to be paid 100 and have to pay 250,
which means that his payment is going to be 150.
Well, we know that he has a dominant strategy to tell the truth.
But what if both Agents 1 and
2 could coordinate to change their declared valuations?
What if for example they were each to increase their valuation by $50?
Well, in this situation it actually turns out that both Agents 1 and
2 are better off.
Their payments both go down by $50.
How does that happen?
Well, it turns out that Agent 2's change of declaration reduces the payment for
Agent 1.
And Agent 1's change of declaration reduces the payment for Agent 2.
So if they can collude together, they can both reduce their payments,
and this doesn't violate our claim that they have individual dominant strategies,
but it is a problem for VCG.
So we have to be sure that we don't use VCG in situations where it's easy for
agents to collude.
So, the next problem with VCG that I'd like to tell you about,
is, again has to do with the payments.
And we say that VCG is not frugal because the payments can really seem out of line.
So let's think again about this graph routing example that we've seen before
where we want to find the shortest path and pay agents for
routing traffic along their edges.
So recall in this example that the shortest path is this one
with a cost of five.
And recall also that the second shortest path is this one with a cost of six.
2 plus 3 plus 1.
Now let's think, in particular, about the effect on agent AB,
of changes to AC's cost.
And what I'm going to end up showing, you is that VCG can end up paying
arbitrarily more than AB is willing to accept,
because AB's payment doesn't end up depending on his own declaration, but
instead ends up depending on the cost of the next shortest path.
So, and this is also a possible problem in
cases where we're not paying the agents, but rather where the agents are paying us.
So let's see how it works.
So if for example the cost of this edge was to increase to 8,
then here our cost would be 12.
Our second shortest path cost would be 12.
And so that would change the payment to AB and it would go up by six.
So we increased this value here of somebody else's value by six and
although we didn't change anything about what AB was willing to accept,
we ended up changing our payment to AB, also by six.
And indeed, if the cost was any x greater than 2 for
this edge AC, then we would end up making
a payment to AB which depends on x and doesn't depend on AB's own value.
So this means that the gap between agents' true costs on the payments they
could receive under VCG is unbounded.
Now, we might think that we're just comparing to the wrong thing.
We might think that we really can't do anything about the fact that
VCG is going to not be able to charge the people based on their own values.
But we might hope that VCG's payments are close to the cost of the second shortest
destroying path.
And it turns out that that's not even true.
So here's a different, a little bit more complicated graph,
that will illustrate that point.
So here I have two disjoint paths.
This one here goes through k agents, and each agent has a cost of c over k.
So k times c over k means the total cost is c.
Here I have another edge with only one agent,
and his cost is c times 1 plus epsilon.
So as long as epsilon is a positive number,
the top path is going to be shorter than the bottom.
So, VCG picks the top path, and it pays each of the k agents this amount here.
So it charges each of the k agents the costs of
the other agents on the shortest path, and
then it pays them the cost of the guy who doesn't get picked.
And if we just rearrange this, do a little bit of algebra and
compute VCG's total payment by multiplying this amount by k,
you can confirm that this amount here is VCG's total payment here.
Well, that's kind of bad news because compare this value here to this value.
And you'll see that VCG's payment Is theta of k
times the cost of the second shortest path.
So what that means is, it differs only by a constant away from being k times bigger.
And now we're comparing actually to the second shortest path.
So it really seems like VCG can end up paying much more than is sensible.
Here's a fourth problem with VCG.
Let's think about the notion of revenue monotonicity.
This is a concept that seems very intuitive and natural to us for
a mechanism.
That the revenue that a mechanism would obtain
would always weakly increase as I add agents to the mechanism.
So you might kind of intuitively think that if I'm running a mechanism,
it's always good to attract more participants to the mechanism because
that can only increase my revenue.
But it turns out this isn't true under VCG.
So let's go back to the road building example with different numbers.
Here we see a case where the utility for building the road is 100,
the aggregate utility.
The aggregate utility for not building the road is 90.
And so we would choose to build the road, and we would charge Agent 2, 90.
Because that's the amount of utility that Agent 1 would have if Agent 2
wasn't around.
So far so good.
And now let's consider adding another agent.
And in particular, let's add an agent who has the same utility as Agent 2.
Well, this changes everything.
Because now, if I drop either Agent 2 or Agent 3, then,
I'm still going to end up in a situation where I make the same choice.
That means, neither of these agents is pivotal and because they're not pivotal,
they don't pay anything.
So, now nobody has to pay anything.
So what this means is that adding another agent to my mechanism didn't change
the choice that was made by VCG.
But caused it to go from a positive amount of revenue to zero revenue.
Another way of seeing why this could be a problem, is that Agent 2 could pretend to
be two agents if he was able to submit a bid to the mechanism under a false name.
And if he could do that, he could eliminate his own payment.
So, with the problem with collusion which seem that if two agents can kind of behave
like one agent in VCG, we've got a problem.
Here we see that if one agent can behave like two agents, we've also got a problem.
Here's one last concern about VCG.
Sometimes we might want to use the mechanism as in the road building example,
just as a way of making a social choice.
Not at in order to actually collect money from the agents.
And if this is the case, I might actually not really want to keep
the money within the mechanism, maybe even the mechanism is just a computer program,
it's not even something that's able to hold on to the money.
So I might like to rebate the money back to the agent somehow.
And the problem is, that if I just give all the agents a rebate,
kind of no matter how I do it, it ends up changing the agents' incentives.
So the agents start behaving differently in order to change the amount of
the rebate they get, and it ends up breaking VCG.
So for example, even if I say,
I'm going to take all of the profits that VCG makes and give them to charity.
Well, if the agents care about the charity, then
they're going to care about what happened and that's going to change their utility.
Or if I'm going to just take the money and go down the street and
buy myself something.
If that benefits the local enemy and
that benefits the agents, then that's going to give them new incentives.
So kind of formally what I have to do is burn the money.
I have to take the money and just kind of destroy it in a way that has
no consequences for the agents so that I don't give them the wrong incentives.
Now, I should give you a caveat.
It actually is possible to return some of the revenues to the agents, but
it's very tricky to do this and
in general what's not possible is to return all of the money.
So there are ways of returning some fraction of the money,
which is discussed in the literature, but
in general it's not possible to just hand back all the money to the agents.
So overall we've seen that despite the great properties that VCG has,
there are also some caveats with it.
Now I should mention that some of these caveats are problems with mechanisms
other than VCG as well.
So although I've pointed out some problems here, I don't want to leave you with
the impression that these are problems only with VCG.
But in general these are things that one should think about
before making a choice of mechanism.
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.
