And in particular, let's think of, we've got our society with N,

individuals, finance set of outcomes, O and if we

begin to think about designing mechanisms in this world And we want one more.

Every agent has a dominant strategy for each preference.

We can invoke the revelation principle.

And the revelation principle tells us that if we do have an indirect mechanism

that has dominant strategies we can.

And just collapse that into a social choice function,

a direct mechanism where people just tell us directly their preferences and

then we give them the outcomes that would have gotten through the original mechanism

for each announcements of their preferences.

So if they had followed the strategies that they had, dominant strategies and

original one.

So this makes truth of dominant strategy so

the revelation principle will means that we can without loss of generality for

this exercise look at social choice functions directly, okay.

And so, now what we want to do is think about which social choice functions can

a society have which are going to be dominant strategy truthful and make sense.

Okay, well.

So, it's, this things are also known as non-manipulable.

Strategy-proofs, sometimes they're called straight forward mechanisms or

social choice functions.

And the important result in this area,

due to Allan Gibbard, Mark Satterthwaite in the early 1970s,

is going to say we're going to have a really hard time doing this

in a setting where people can have any possible ranking over the alternatives.

So let's have a look at that.

This is what's known as the Gibbard-Satterthwaite Theorem.

And it's another form of an impossibility theorem similar to what we saw in terms of

Arrow's theorem and the theorem.

So situations where we have a set of conditions we'd like to have and

the theorem says,

it's impossible to have this desirable set of conditions all at ones.

So what's the setting here?

We've got a social choice function,

we'd like to have one that's mapping all possible preferences.

So people have linear orders, they can have any strict ranking of our candidates.

And we're going to look at situations with a least three outcomes,

so we have at least three candidates to choose from.

And we're going to also look at a social choice function which is on to.

That means for every possible outcome,

there is a profile of preferences which gives you that outcome.

And that condition can be satisfied quite easily.

For instance, if you just required that your social choice function be unanimous.

So if all individuals prefer the same alternative,

we all say we love candidate a, then this is how you should pick candidate a.

If you put that minimal condition in, then indeed the,

in this domain of preferences, c is going to be on to.

So if we put those conditions then what does the theorem say?

The theorem says, that we're going to have the strategy in this condition,

truthful reporting of preferences is a dominant strategy for

every agent at every preference profile, if and only if c is dictatorial, okay.

So again, that means here, there is some particular individual I for

whom the choice function is just always their favorite alternative there

the thing that maximizes their preferences and regardless of what anybody else says.

So we just pick one individual.

We just listen to that person, okay.

Now in terms of the proof of this, it's clear that if we assign somebody to be

a dictator and don't listen to anybody else, that's going to be strategy proof.

Right, nobody else can make any difference,

doesn't matter what they say and the person who is a dictator

always wants to be truthful because they're getting their favored alternative.

The converse of this theorem is much more difficult, the part saying that if it's

strategy proves then it has to be dictatorial and this can be proven by

various means there are proofs that relate this back to Arrow's theorem and

show that there are similar conclusions

they can get in terms of the basic steps dilemmas that where approved in there.

There's a very elegant proof by Salvador