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.

Â