3.3 VCG: Examples

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

Let us look at an example of VCG in action,

of the Victory-Clarke-Groves mechanism in action.

And it'll be a routing, a transportation problem.

So here is a directed network of links,

each link have the cost of the length of it if you wish and

the goal is to find a shortest path from A to F.

And obviously looking at it,

be quite obvious that the shortest path is this one.

So this is the path that would be selected

by a traveler who wishes to get there, from A to F most quickly.

Now, according to VCG, how much

would the owner of the link AF pay?

Well, intuitively he's not part of the, or

the path, so he shouldn't have to pay or receive anything.

Let's see what VCG says.

So the shortest path with AC's declaration of what their cost is, is five right.

And so the cost to all the agents is that

shortest path totaling five.

Had AC not been in the picture, and not declared anything therefore,

what would the total cost to the agent have been?

Well, it would have been the very same path, so the shortest path.

And so the cost would have been 5 also and so,

the amount that AC pays, if you wish, is the difference

between the cost to the agents within the picture and

the cost without in the picture which of course is 0.

And this is true for

all the other edges that don't participate in the shortest path.

All these edges.

Let's draw them blue.

These edges not participating in the shortest path

will neither pay nor receive anything according to VCG.

So that's the easy part.

What about edges that do participate in the shortest path?

So let's look for example at one of them, at AB.

Well, with

the shortest path as we know is this one.

And how much would all agents other than AB itself,

what is the cost on the agents on this sort of path?

Well, it's 1 + 1, is the cross of two.

Had AB not been in the picture, what would have happened?

Well the shortest path would have been this one over here.

So this wouldn't be the shortest path of a cost of 2+3+1.

And so the cost to the agent AB is

the difference between the cost without

them in the picture, which would be -6 And

the cost with them in the picture, which is -2.

That is the cost to all the other agents and the difference is -4.

So the cost to AB is -4, in other words AB will

get a payment of 4.

Making, if you wish, a profit of 1 because the cost is 3,

you'll get a payment of 4 and you'll have a benefit of 1.

So this is for AB.

What about BE, for example?

Well it's the same sort of analysis.

BE the cost to all other agents

without BE in the picture is -6.

Its still, this would have been the shorter route

had BE not been in the picture and cost would be -6.

Now the cost to the agents with B in the picture,

to the agent other than BE is 4.

Why is that?

It's 1 + 3.

And so the cost to, this is the -4 over here, so

the neck of it is that the cost imposed by VCG

on the link BE is -2, in other words, they would

get a payment of 2, making, again, a profit of one if you wish.

What about EF?

Same sort of calculation, although the outcome would

be a little different because in that case they will getting a payment of 3.

Why is that?

Well without them In the picture this would no longer be the shortest path.

So the shortest path would be a cost of 7, whether it's this one or

this one, in both cases the cost of the first path will be 7, so

the total cost to the population, without them in the picture, would be 7.

With them, the cost is again the 1 + 3,

it's a 4, and so they get the difference of 3.

So the payment would be 3 and

therefore the net profit, if you wish, it would be 3- 1, namely 2.

So you could ask why are, why is it so different.

You look at all these links somehow their net payoff is different.

Is that fair and fairness is in the eye of the beholder.

But the rationale for it is that they have different market power.

The amount of social value they bring is different

because without them, the outcome would be different to the population and

that's why they have a different sort of payments and

different cost structures here.

That's an example of DCG in operation.

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