0:00

Hi folks, it's Matt again.

So what we're going to do now is look at a few examples that'll illustrate some of

the notation and definitions you've seen in terms of mechanism design, so

let's go through that.

So, let's look at a particular example.

And this is going to be an example where there's a society of people making

a decision over a candidate.

So, they're electing somebody.

So we've got the N that we talked about,

is now a committee of voters, so we'll index them 1 through n, little n.

And those are maybe people in legislature,

they could be people in a town, they're people making a decision over a candidate.

0:38

Here the outcomes now are the candidates.

So, we'll label them a, b, c.

So in this case let's keep it simple,

we'll have three candidates who could possibly be elected.

In this example,

what we're going to be looking at is one where there's private values.

So, the people involved have preferences where they know their own preferences.

So, the types that we looked at before,

these theta I's, fully capture all of the preferences of the agent.

So, for instance, there might be some type of a particular agent, say, theta tilde,

which is one who likes candidate a the best, b second and c third.

And in this case, we'll keep things simple, 3 units of utility for

a, 2 for b and 1 for c.

So that would be one possible utility.

So then in terms of our notation, that means that the utility function here for

I as a function of the outcome and

theta tilde depends only on the person's own type.

So it doesn't matter what other people's types are in terms of

determining that utility.

1:41

Okay, so in this particular example then, that means that ui of a,

and theta i is 3, b and theta i is 2, and c is 1.

In this case, we should have subscripts on the use.

So this is a simple way of representing it.

This is private values.

So that means that the person doesn't need to know the other person's types in order

to figure out what their utility is.

They know how they value the candidates, and

there's no information out in the society that would change that.

Okay, so what we'll do in this example is keep things very simple again.

We'll have three possible types.

So there's the theta tilde, who likes a the best.

There's another type, theta hat, who likes b the best.

And a type, theta bar, who likes c the best.

So in this case, theta tilde likes a, then b, then c.

2:33

Theta hat likes b, then a, then c.

And theta bar is a c, then a, then b.

Okay, and we'll look now at what the implications of that are going to be for

the voting.

So, in terms of probabilities,

let's think of a world where most of the people are either tildes.

The people who like a the best.

Hats, that people who like b the best.

And there's a small percentage of the population who are people who like c.

And we'll think of these as distributed independently across a society.

So each person gets their own draw.

And knowing your own type doesn't tell you anything about what the rest of

the society looks like in this particular example.

3:14

So, now let's talk about what a mechanism looks like in this world,

in terms of the notation.

So here, let's think of plurality voting, so a very common voting system.

Each person just picks which candidate they'd like to vote for,

and the rule picks the candidate named by the most agents.

So this is probably one of the most simple and economical of all voting mechanisms.

And in this situation, our actions for

each player, each agent in society, is just a list of the candidates,

so they can declare that they vote for a, b, or c.

Then the mechanism takes those announcements

that the people have made and makes a choice of outcomes, which could be random.

And in particular, if for instance the votes were b, b, and c,

then it would pick candidate b.

That would be the person named by the most.

If there's some tie, then it's going to randomized and

it's going to pick among those getting the most vote.

So for instance if you had a society that split to third a, b, and

c's, then it would pick each candidate with probability 1/3.

So that's the outcome function, which is mapping from

the announcements of the agents, into some distribution over outcomes.

Okay, so now we've got our mechanisms and so forth.

And so now we can talk a little bit about the solution of one of these.

So how are people going to behave in this society?

So first of all,

let's note that there aren't any dominant strategies to this mechanism.

So, to think about that,

let's think of a world where we've got an odd number of voters.

So, we're not going to have to worry about people,

that'll make our life easier in terms of ties.

5:01

So, let's consider the type theta bar I.

This is the person who likes c the best.

And then a n and b.

Okay, so what's that person's choice?

Should they be always voting for c?

Well, that's not completely obvious, right?

So if half of the other voters voted for a and half of the other voters voted for b,

then that's a situation where now they're going to be the decisive voter.

If they vote for a, a wins.

If they voted for b, then b would win.

If they voted for c, then it would be a runoff.

It would still be that a and b would be tied,

because there's at least five voters.

That means that there's at least two votes.

So we've got at least two votes for a, at least two votes for b, and no votes for c.

So, that means that if this person votes for a, a wins.

They vote for b, b wins.

If they vote for c, it's going to be a coin flip between a and b.

They prefer a over b, so they should vote for a, right?

So then they're best off voting for a in this situation.

6:01

In contrast, if you go through the same calculation of half the other players

voted for c and half voted for a, then you're better off voting for c.

So what this tells us is that how this person votes actually depends on what

they're thinking the other people in the society are going to do.

So if they think the other people are splitting between a and b,

they should be voting for a.

They think that other people are voting for c and a,

they're better off voting for c.

So this means that there's not a dominant strategy in our standard

sense in this kind of game.

Okay, so when we start thinking about this, and actually just here,

that you can go through.

Here, there wasn't any dominant strategy when we're in a situation where there was

at least five people voting.

If you go through this same kind of reasoning,

think about what's the case with n = 3.

So that'll test your understanding of this.

Think a little bit through how this person should be behaving

in the case where there's actually just three voters.

So there's many Bayes-Nash equilibria to this game.

So in particular, for instance, everybody voting for candidate a is an equilibrium.

Why is that an equilibrium?

Because if everybody else is voting for candidate a, then regardless of what I do,

there's going to be a majority of people for candidate a.

So, I might as well vote for candidate a.

It really doesn't matter what I do.

Similarly, everyone voting for candidate b is an equilibrium.

So these will both be Nash equilibria.

You're also going to have one where everybody votes for candidate c.

Here I put it that this isn't sensible.

Why isn't this sensible?

Well, it's not sensible in the sense that if I'm the theta bar type,

then b is my least preferred alternative.

And I'm only doing this because I think that my vote has absolutely no chance of

making a difference.

If it had I small chance of making a difference,

then instead I should be voting for a or c.

So, if you put in a requirement that nobody plays a weakly dominanting

strategy, then that would eliminate these kinds of equilibria.

There are also other equilibria.

So here's the two candidate equilibrium.

So, let's think of the types who prefer a, vote for a.

8:05

All the types who prefer b, vote for b.

And then there's this third type who actually likes c the best, but

all of those types vote for a.

Now why is this an equilibrium?

Well, if we're in a world where all the types know that

the votes are only going to be cast for a or b, then voting for c is a wasted vote.

It's not going to have a consequence in terms of getting c elected, and

it leaves the votes then determinant between other people's votes for a and b.

Therefore, if there is a chance that my vote makes a difference,

it's always going to be between a and b,

I might as well vote for my most preferred alternative out of those two.

And therefore, in this case, the theta bar type

has a unique best response in this case to actually vote for a.

So this kind of equilibrium actually is referred to as

Duverger's law in the political science literature.

And it refers to the fact that plurality systems of this

type often result in basically, only having two viable candidates.

Because you realize that if there's a third candidate who has a low probability

of being elected, you're better off casting your vote for

one of the two candidates who are really in contention.

And that focuses all the attention on two candidates, and it's really hard for

a third candidate to enter and have any chance of winning.

That's known as Duverger's law, and

you can begin to see it in this type of equilibrium.

But basically, plurality rule have lots of Bayes-Nash equilibria.

9:36

Okay, so now when we think about the definition we had for direct mechanism,

these were ones where people were not reporting their preferences.

What they were reporting was an actual vote.

But we can think of the direct mechanisms for plurality rule.

So instead, let's think of a mechanism where the voters actually are just

going to tell you what their type is.

So they're telling you their ranking of the three candidates,

whether they're a theta tilde type, a theta hat type, a theta bar type, etc.

Then the mechanism is going to translate those into votes.

So theta tilde, is as if you're voting for a.

Theta hat is as if you're voting for b.

Theta bar is as if you're voting for c.

So the mechanism takes your announcement of types and

then actually translates that into a vote.

This is one possible direct mechanism.

It could, instead, be one where saying theta bar translates into a vote for a.

So we could change the mechanism.

This is one of the possible mechanisms.

This particular mechanism is actually going to be manipulable,

in the sense that if other people are truthful,

then the theta bar type would actually prefer to vote for a.

So they won't say that they're a theta bar type,

because that's as if they're voting for c.

That's a wasted vote when, remember,

there's 49% of the types are of the theta tilde type,

49% are of the theta hat type, and only 2% are of the theta bar type.

So, they're expecting most of the people to be voting for either a or b.

That's going to be a situation where announcing truthfully if you expected

everybody else to be announcing truthfully,

wouldn't be a best response, right?

They're not going to want be truthful.

They're going to want to say, theta tilde, because the chance is that the decision's

really going to come down to one between a and b, and

c's really not going to be in the running.

So this is just one example of a direct mechanism,

in this case that direct mechanism is manipulable.

11:33

Okay, next what we're going to do is look at other kinds of direct mechanisms,

and talk in general about the revelation principle.

Which talks about the relationship between these indirect mechanisms,

where you're doing votes or maybe sending some complicated message.

And ones where instead, you just directly report your type and

will map an equivalence between any particular general mechanism and

revelation mechanism.