3.4 VCG: Limitations

Loading...

En provenance du cours de Stanford University

Game Theory II: Advanced Applications

336 notes

Stanford University

Game Theory II: Advanced Applications

336 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

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.

Télécharger dans l'App Store

Disponible sur Google Play