3.5 VCG: Individual Rationality and Budget Balance in VCG

Loading...

En provenance du cours de Stanford University

Game Theory II: Advanced Applications

306 notes

Stanford University

Game Theory II: Advanced Applications

306 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

We've seen in the past that the VCG mechanism

gives rise to dominant strategies and efficient allocations.

We know that in general it doesn't give rise to individual rationality or

budget balance.

In this video we'll see that under some pretty mild additional assumptions

it is possible for us to get both of these things.

Now remember that individual rationality means that it makes sense for

agents to participate in a mechanism.

If they had a choice between participating and

not participating they would be happy to participate.

And recall that budget balance means that it doesn't cost money to run

the mechanism.

The mechanism either completely breaks even all the time,

which we've already seen in the previous video is impossible for VCG, or

at least is weakly budget balanced and turns a profit or breaks even.

What we'll see in this video is that we can have both these two properties.

So let me start with individual rationality.

To get individual rationality,

I'm going to need two different assumptions to be true of the environment.

The first is called choice-set monotonicity.

And this assumption says that for

all agents, the set of outcomes that are achievable without that agent present.

Is a weak subset

of the set of outcomes that are possible when that agent is present.

So, in other words, when I remove an agent from the mechanism, as,

of course I have to do inside the payment evaluation for VCG,

the mechanism set of choices that are available to it weekly goes down.

So no, in particular no new choices become possible when somebody gets removed.

The second assumption that I'll make is called no negative externalities.

And I'll say that we have no negative externalities.

If for all agents and all choices that can be made without that agent

the agent's own valuation for each of these choices is non-negative.

So, in other words, when you get dropped from the mechanism, it isn't possible for

the mechanism to choose something that actually causes you pain.

It might choose something that you like less well than what it chooses when you

are present but it can't choose something for which you have negative utility.

Let's look at two examples of realistic scenarios that satisfy both of these

properties to give you a sense of why these properties are reasonable to assume.

So the first is the road-building referendum problem.

So consider this problem where we want to have a vote between agents

to decide whether or not to build a public good like a road.

So, the set of choices has nothing to do with the number of agents.

Because the two choices are that either the road gets built or

the road doesn't get built.

Remember that the payments come from the payment function those

are not the choices.

And so the choice set is monotonic.

It's monotonic in the weak sense that it just doesn't change within a but

remember that we allowed for a weak subset.

Secondly, let's assume that no agent negatively values the project.

So, some agents might like it better for

the road not to be built than for the road to be built.

But let's say that none of the agents experiences negative utility in

any situation.

That still seems like a reason what model of this problem and

that would give us no negative externalities.

Okay, well we saw an example previously where choice-set monotonicity

arose in a pretty trivial way because the set of choices just didn't change.

Let's look at a richer example where the set of choices does change.

So here let's think about kind of a simplified stock market in which

we have two different kinds of agents.

Some of them have a single unit of a stock that they want to sell.

So they have one share of Apple stock and they want to sell it.

We have another group of agents who want to buy one share of Apple stock and

we have some number of agents on both sides of the market.

Now the choices that the mechanism can make here

Are different ways of paring together buyers and sellers.

So every buyer can interact with only one seller.

Every seller can interact with only one buyer.

And nobody has to interact.

So the pairing where nobody gets paired is valid.

The pairing where just two people get paired is valid.

And pairing where as many people as possible get paired is valid.

So we have these various different ways of establishing trades that might happen in

this market.

Now, think about what happens if I add a new agent to the market,

none of the pairings that worked when that agent wasn't present

go away when I add a new person.

They're all still possible to do because I could always just set that

new person aside.

But, I can also have that new person participate in trades

that weren't possible without that person there and thus, you can see here

the choice-set monotonicity is satisfied in a more interesting way because

new options become available when I add an agent but no old options get rolled out.

And it's natural in this kind of a setting to assume that agents have zero utility

both for other people trading with each other and

for other people not trading at all.

And that being the case, the agent has zero utility for everything that

can happen when they are not present and so there are no negative externalities.

So now we are ready to consider the main result that we want to establish for

this part of the video Which is that these two assumptions that we've just

made of choice set monotonicity and no negative externalities,

are sufficient to make the VCG mechanism exposed individual rational.

Now let's remember what exposed individual rational means.

As I said at the beginning of the video, individual rationality means that agents

always have weakly positive utility for participating in the mechanism and

ex-post means that this is true regardless of what

valuations any of the agents have so this is true for every realization

evaluations that the agent himself and also all of the other agents might have.

So this is the strongest kind of individual rationality, so

this is the most desirable property about individual

rationality that we would hope to prove about VCG.

And that makes this an encouraging result.

So here's how we prove it.

We begin by saying that all of the agents truthfully declare their valuations in

equilibrium because we want to think about what happens in equilibrium.

And then we can write this expression for age and

Isaac expected utility for participating in the mechanism.

Well, he gets his value for the allocation that actually happens.

So this is the choice that VCG actually makes

given that everybody reports their values truthfully.

And he gets his value for that choice and

then he pays the VCG payment function that we all know and love.

So because I've assumed that everybody reports truthfully,

I don't have any V-hats anywhere.

So I can collect terms and, particularly, I can roll this into one of the sums.

So I here get a sum over all of the agents,

minus a sum over all of the agents except for I.

Now it comes the part where I use choice-set monotonicity.

So remember that this expression x(v) is the outcome

that VCG chose which means that it maximizes social welfare and

by choice set monotonicity, this other outcome x(v-i)

was also one of the available choices when we pick this instead.

And so what that means is there must have been at least as much social welfare

arising under this choice as under this choice.

If not, the optimization would have just picked this one.

And so writing that as an equation,

the sum of agents values for

this choice is at least as big as the sum of equation values for this choice.

I'm just moving that equation up here, and

now I can also use no negative externalities.

Let me just write the definition of no negative externalities so

the value that I has for

the choice that gets made when he's not present is greater than or equal to zero.

And what that means is if I change this expression here to j

not equal to i then I've just taken out a non-negative number here which

means that this whole thing got smaller and that means the inequality still holds.

And so I have this expression here and that's exactly what I wanted to prove

because remember the agent's utility is this expression and so I want to ensure

that this number is bigger than this number If it is then this whole thing is

positive and I have individual rationality and that's exactly what we just find here.

That this infact is positive or non-negative and

so we do obtain individual rationality.

Okay, so much for individual rationality, now I want to talk about budget balance.

So here's the property that we need, turns out that one property is enough,

for showing that VCG is weekly budget balanced.

And we call this no single-agent effect.

So an environment exhibits no single-agent effect if it's the case that for

all agents I.

All evaluations of the agents other than I that are possible and

all choices x that maximize the social welfare.

There exist another choice x prime

which is feasible without i which means it's possible for

us to pick it even if i has been dropped and for which all of the agents

other than I get more social welfare than under the original allegation.

So, in other words if I drop an agent I and

then I pick some other choice instead we owed i.

Everybody other than I is at least is happy with the new choice as with

the old choice.

So the welfare of agents other than I is weakly increased when we drop I.

That might sound a little confusing, it's actually a really natural property.

Here is an example.

Think about a single sided auction where for example I have one good for sale.

The choices in these case are all of the different agents I could give the good to.

And if I drop an agent, one of two things is possible.

Either that agent wasn't winning the auction before in which the social welfare

maximizing outcome remains the same after the agent has been dropped and

nothing changes.

And so then I get equality in this expression.

Or that is the agent who was winning before and

then I pick a different winner once that agent has been dropped.

I'll get less social welfare overall which is why I was picking a different agent

in the first place.

But when I consider only agents other than i

they're all going to be happier when i has been dropped than when i was present.

Because one of them gets to win after I is dropped.

And in the case where i was present one of them wasn't winning.

So if you can see it's kind of actually a pretty natural property,

this no single-agent effect.

So it turns out that this is all we need to prove that VCG is weekly budget balance

and indeed that's a pretty direct proof.

So as before let's assume truth telling an equilibrium.

And now what we want to think about is the sum of transfers that agents make

to the center.

So the sum of all of the payments.

And I want to show that this sum of all of these payments is greater than or

equal to zero.

That's going to mean weak budget balance.

So once again, this is the VCG payment function and

now I'm just summing the payment function across all of the agents.

Because I'm interested in the aggregate payment.

From the no single agent effect condition, I know that for

all of the agents other than I.

The value they have for the choice they gets made when I is dropped.

The social welfare maximizing choice for them, they gets made when i is dropped,

is at least is beg as the sum overall of their

utilities for the choice that gets made when i is not dropped.

That's just directly what no single-agent effect means.

And you can see that these are exactly the terms that I have in the VCG payment

function.

And so the result follows directly.

This blue term is bigger than the green term which means that this

expression up here is just positive for every i or non-negative for every I.

And so that gives us what we want which is that this whole sum is greater than or

equal to 0.

Well, I have one last bid of good news to give

you here's a theorem from Christian and Perry.

Which says something else about the revenue and

VCG which is even more encouraging the one that what we just saw.

It says consider any Baysian games settings in which VCG is

exposed individually rational, and

the claim is that in such a case VCG collects at least as much revenue

as any other efficient and ex interim individually rational mechanism.

Now here are a couple of things to kind of walk through

about what is being claimed here.

First of all, you might wonder about this little preamble, didn't we

already talked about what happens when VCG is ex post to individual rational, well,

not really because what we looked at before,

was two conditions that are sufficient for VCG to be individual rational.

We didn't claim that there are other things that might be true about

the setting that would also result in VCG being individual rational so

what this theorem says is don't worry about how you got there,

think about any setting in which VCG is ex post individually rational, it

will include what we talked about before but it'll include other settings too.

And what is says is VCG collects at least as much revenue

as any other efficient mechanism.

The thing to notice here is

even if that mechanism only uses Bayes-Nash equilibrium.

We're not assuming that this other mechanism is dominant strategy efficient.

So this other mechanism gets to be drawn from a much bigger pool,

the dominant strategy mechanisms and the Bayes-Nash equilibrium mechanisms.

And another sense in which it's drawn for a bigger pool is that we're only going to

require of this competitor mechanism that it's ex interim individual rational

whereas, we're requiring a VCG that it's ex post individual rational.

So, this is ex interim individual rationality is a weaker thing to require

which means,

there's a broader set of mechanisms that would satisfy it which means that we're

making a stronger statement when we compare VCG to this broad set.

So, a way of understanding this result is that VCG is as

budget balanced as any efficient mechanism can be.

So I'm not saying here necessarily that the revenue is greater than or

equal to zero.

Sometimes it will be and sometimes not.

But in cases where the revenue is still negative.

Well, this results as is if VCG was ex post individual rational.

There's no other mechanism which is efficient and which get's more revenue.

So, VCG is always getting it's close to budget balance as efficient mechanism can.

As long as VCG remains individually rational.

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