2.4 Revelation Principle

Loading...

En provenance du cours de Stanford University

Game Theory II: Advanced Applications

305 notes

Stanford University

Game Theory II: Advanced Applications

305 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

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

Rencontrer les enseignants

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

This video is going to tell you about the revelation principle

which is one of the core ideas that makes mechanism design possible.

So let's begin by finding out what the revelation principle says to us.

It says that any social choice function that can be implemented at all by any

mechanism can also be implemented by a truthful and direct mechanism.

So let's recall what it means for a mechanism to be truthful and direct.

We say that a mechanism is direct

if it works by having all of the agents simply make a single declaration,

you can think of it as writing something down on a piece of paper.

Given that to the person who runs the mechanism and

having some decision be made.

An indirect mechanism in contrast, might have a whole sequence of actions and

information revelation and subsequent actions that depend on that information

revelation, multiple actions by different agents.

An indirect mechanism is essentially any

sort of imperfect information Bayesian extensive form game.

In contrast, a direct mechanism is a simultaneous move Bayesian game.

So it's kind of like a sort of Bayesian version of a normal form game.

Now a mechanism is truthful, a direct mechanism is truthful if

the equilibrium strategy for every agent is when they have to write something down

on that piece of paper is just to write down all of their private information.

So, simply to declare what their type is.

So a truthful mechanism gives agents, the very easiest,

strategic problem that they can have.

Write me down something on the piece of paper, and

the agents say, all right, I'll tell you all of my secrets.

I'll just reveal everything to you on the piece of paper, and you go off and

make a decision based on that.

And, what the Revelation Principle tells us, kind of surprisingly,

is that if I can implement a social choice function in any complicated way

I can also implement it in this very simple, truthful direct way.

So let's see how this works.

I start with an arbitrary non-truthful mechanism, which indeed may be indirect.

So let me draw it here.

So what happens is all of the agents

have some types because we're in a Bayesian game setting.

Then they each take some strategy, which is a function of their types

that tells them how to behave inside this mechanism.

And then some complicated thing happens in here.

Maybe we have information revelation, there's all kinds of,

maybe repetitions of agents acting multiple times.

And then in the end eventually something happens, the mechanism decides an outcome.

Well, recall that we can look at this whole thing as being a game, right?

In the end this is just a mapping from agents types and

strategies into some outcome that the agents have utility for in the end.

And so I can think about an equilibrium of this game, it's just some Bayesian game.

And so I can think about theses Ss all being in equilibrium with each other.

And that's exactly what I do when I talk about implementation,

if I say that the mechanism implements a social trace function,

what I'm saying is that any equilibrium the mapping from types to outcomes is

the same as the mapping that would be chosen by the social choice function.

Well, here's the punchline.

I want to show that I can make a new direct mechanism which is truthful.

And here's how I do it.

I take the original mechanism and I kind of embed it in this new mechanism here.

So, what I do is I say I'm going to make a new mechanism

who's action space is the same as the type space.

So, I'm going to ask each of the agents tell me what your type is.

And of course the agents could do whatever they want,

they don't necessarily tell me the truth but they tell me something.

And then I take that type of the declared.

So let me first of all give a name to that.

So I call the policy that agent, I has, for declaring his type to me.

His strategy as prime I which is a function of his true tape, right.

So he has some way of deciding based on his tape how to reveal something to me.

So, he'll come up with some type which is a function of the real type that he has,

but maybe it's not the truth.

Maybe he'll tell me something else.

I'll then take whatever he declares to me, and I'll believe him, that that's his

type, and I'll stick that into S, the strategy profile that we had before.

Which is our previous equilibrium in the original mechanism.

So I'll take that type, I'll then figure out what strategy he would have played

in the original mechanism if his type had been what he declares to me.

And then I'll simulate the original mechanism.

So if it's indirect,

inside this new mechanism I'll kind of run a simulation of the new mechanism.

I'll figure out what the original mechanism would've done

if everybody had played their declared types

under the strategies that were previously in equilibrium.

And I'll figure out what the outcome is and

I'll make that the outcome of the new mechanism.

Well, I want to claim that this new mechanism is truthful.

You can see that it's direct.

It's direct by construction.

I want to claim that it's truthful and this should be kind of easy to see.

It's truthful by exactly the same argument that S was an equilibrium.

So if this mechanism isn't truthful, that would mean that S wasn't an equilibrium.

Why?

Because if this mechanism isn't truthful,

then I want to declare some type here that isn't my real type.

And if I'm declaring type mechanism, my real type, that means

I'm changing the strategy that I would have played in the original mechanism.

I'm kind of, I would have preferred to also, if I lie to the mechanism here,

I would have preferred to lie to myself in the original mechanism, so that I

would effectively be playing a different strategy than I was playing before.

And of course, the whole idea of an equilibrium is that nobody can gain by

changing their strategy.

So if I wouldn’t have wanted to lie to myself in the original mechanism and

change my strategy, nor would I want to lie to the mechanism now because it’s

already playing a strategy for me that’s an equilibrium to the original mechanism.

And of course, that being the case,

it chooses the same outcomes as the original mechanism.

So kind of the slogan for the Revelation Principle is that the agents don't need to

lie in this new mechanism because the mechanism already lies for them, right?

We don't actually feed their real types into the original mechanism,

instead we already applied this strategy of their times,

just in the way that they were doing before.

And given that the mechanism is going to do such a good job of lying for me,

just in the way I would have wanted to lie.

There's no reason for me to lie again.

Right? The mechanism is acting

kind of as my proxy.

The mechanism is doing just what I would like to do.

If only I tell it the right thing.

And so I should tell it the right thing.

That's the idea of the revelation principle.

So there's one kind of technical concern to mention here.

Which is that the set of equilibria is not always the same in the original

mechanism and the revelation mechanism.

The revelation mechanism of course has the original equilibrium we're interested in,

that's just what I've shown you.

But it could actually introduce new equilibrium which we don't like.

It's a bit of a technicality, but it's worth telling you.

But let me give you the high level point here,

which is that the revelation principle really is important for mechanism design.

So why?

What is it good for?

Well, there's kind of three ways to see it.

It tells us the truthfulness is not a restrictive assumption

from the point of view of what can be implemented.

Likewise, it shows us that direct mechanisms are not

less powerful than indirect mechanisms, which is a bit surprising,

because it sort of feels like direct mechanisms are much more rich and

complicated, and they ought to be able to do more.

So this tell us no, truthful and direct mechanisms are enough.

If you can show that something is true for truthful and

direct mechanisms, you've also shown that it's true for all mechanisms.

And that's really important for analysis.

So if I want to prove something about the space of all mechanisms.

In principle, that might seem really hard to do because I would have to grind

through every possible non-truthful indirect mechanism.

Seems like a hard set to think about.

So, what the revelation principle tells me is that if I want to prove that

no mechanism exists with certain properties or

that some given mechanism is the best one that exists with certain properties.

It's enough to show that it's the best one among the set of truthful and

direct mechanisms.

And that's a much more manageable thing to do.

So really the revelation principle in telling us that we can

restrict ourselves to truthful and direct mechanisms without loss of generality

opens up the analysis of mechanisms.

And we're going to see in the future when we prove things about mechanisms.

We always begin by saying without loss of generality let's restrict ourselves to

truthful and direct mechanisms.

And that stuff is very important.

That would makes mechanism design feasible in practice.

And so, that's why we're telling you about this so early on.

This is a really important foundational principle to mechanism design.

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