2.5 Revelation Principle: Examples

Loading...

Do curso por Stanford University

Game Theory II: Advanced Applications

346 classificações

Stanford University

Game Theory II: Advanced Applications

346 classificações

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

Na lição

Mechanism Design

The description goes here

2.1 Mechanism Design: Taste 3:18

2.2 Implementation 18:01

2.3 Mechanism Design: Examples12:00

2.4 Revelation Principle 9:23

2.5 Revelation Principle: Examples5:18

2.6 Impossibility of General Dominant-Strategy Implementation 11:26

2.7 Transferable Utility 9:05

2.8 Transferable Utility Example8:31

2.9 Mechanism Design as an Optimization Problem 19:03

Conheça os instrutores

Matthew O. Jackson
Professor
Economics
Kevin Leyton-Brown
Professor
Computer Science
Yoav Shoham
Professor
Computer Science

Hi folks this is Matt again.

So we're going to look at some examples now of the revelation

principle you've just seen.

And in particular let's go back to the plurality

rule that we looked at just before in terms of an example.

So remember we have a society of people who are voters.

They are trying to make decisions between some set of candidates.

So they are tying to make an election here.

And, in particular their were three types of individuals,

those who liked A, those who liked B, and those who liked C.

The C types favored A over B.

They are a small part of the population.

So remember that was our example.

And we looked at an indirect mechanism, the plurality voting mechanism,

where what the actions look like where reports of a candidate.

So you just declared which candidate you wanted to vote for, and

then the mechanism picked the candidate named by the most agents.

Or in cases where there was some tie among getting the most votes,

then it would pick randomly among those with uniform probability.

Okay.

So, that was the plurality mechanism.

And now the revelation principle tells us for

any equilibrium of that mechanism there exists an equivalent direct

mechanism which will have truthful announcing as an equilibrium.

So remember her there were many Bayes-Nash equilibria.

There will be different direct mechanisms for each one of these equilibria

in terms of translating the outcomes from the equilibrium and

the direct mechanism into an equilibrium in the direct mechanism.

So let's go through that.

Remember that we had, we looked at different types of equilibria say

all voting for A was an equilibrium, all voting for B was an equilibrium.

There was a Duverger's type equilibrium where you concentrate on two

candidates and you voted for your best candidate out of those two.

So the theta tilde voted for A, theta hat voted for

B, theta bar voted for A There's going to be many other equilibria.

We can have all C equilibria.

We can have two candidate equilibrium between B and C and B.

You can get some other mixed strategy equilibria.

But these are more of less the classes of equilibrium.

We can think about for looking at an example of direct revelation mechanism.

So how does that work?

Well now instead of actually casting a vote,

what the voter does is just tell us what their preferences are.

So they make an announcement that they're one of these three types.

Now if we want to think about the indirect mechanism which was

the plurality rule equilibrium where all people vote for A.

So we think of the mechanism plus what the equilibrium was.

Okay. So we can think about one of

the equilibria for the plurality rule.

Equilibrium where everybody was voting for A.

So what's the direct mechanism for that?

Well now each persons states their type.

Now remember in the indirect mechanism everybody was voting for A.

So what happens in the direct mechanism is the direct mechanism translates every

type announcement into the equivalent of the vote for A and the outcome

is just now going to be a independently of what people's types are announced.

So it's as if everybody voted for A, and then the outcome is just A.

Now, truth is an equilibrium, right?

So no matter what I do, it's as if I'm voting for

A, I might as well say my true type.

So this would be the direct mechanism associated with that

indirect mechanism and equilibrium.

Now if we changed it to the equilibrium where people are either voting for A or B,

depending on which was their favorite,

then again the direct mechanism is going to have people announcing their types.

And then what happens is mechanisms going to translate that into

what they would've done.

So it's saying theta told us as if you're voting for

A, theta hat as if you're voting for B, theta bar, as is if you're voting for

A, and then it'll count up how many theta tildes it gets,

how many theta hats it gets, how many theta bars it gets.

And if the majority of votes was for B, it'll end up being a B.

If it was for A, it picks an A.

And now, again, since that was an equilibrium in the indirect mechanism,

this is an equilibrium of the direct mechanism.

Now we see that Taking that same mechanism that we started with.

We have a different direct mechanism for each equilibrium that we had in

the indirect mechanism in order to make sure that things are incentive compatible.

Okay, so that takes us through the direct revelation Mechanisms.

These are going to be very useful for proving theorems because any

equilibrium that we can work with indirect mechanism we always know that there exist

in equivalent direct mechanism that's going to make our life a lot easier.

because it means that whatever we can do with indirect mechanisms,

we can also do a direct mechanism.

And so we can just concentrate on working with those and

making sure that we're getting all the possible outcomes

that we could have gotten with the indirect mechanisms.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play