Updated 17 October 2005

Concept 1. What did Arrow say?

Concept 2. The Borda Protocol

Now suppose that we introduce a new candidate: Buchanan.  We use the Borda protocol as before, but include Buchanan in the set of choices.
   

Notice how Buchanan, the least popular candidate according to the table, tilted the vote in Gore's favor.  This means that the Borda protocol violates the independence of irrelevant alternatives.

Concept 3. Independence of Irrelevant Alternatives, Revisited

In summary, one reason that the independence of irrelevant alternatives is a questionable assumption is that it does not allow a social choice mechanism to unambiguously guess preference strengths from preference orderings, and then use these preference strengths to generate a societal preference ordering.  Toward the end of the lecture, we will talk about another problem with voting mechanisms, namely that they are not truth dominant and this will lead us to the general problem of mechanism design.  Before we do, we will consider several other voting mechanisms.

Concept 4. Iterated Borda Protocol

Buchanan is the least popular, so eliminate Buchanan on the next round.  This means that Buchanan is the least preferred candidate.
 

Bush is the least popular, so Bush is eliminated.  This means that Nader is the most popular.  So, the societal preference pattern is Nader>Bush>Buchanan.

Let's see what happens if we add Gore to the list. It may seem counterintuitive to say that Gore is irrelevant since he wins the most votes, but look at the definition of irrelevancy.  The definition of irrelevant does not mean unimportant; rather, it means that the option is irrelevant in determining the preferences among the other options.
 

Buchanan is again the least popular, so eliminate Buchanan on the next round.
 

Since Bush and Nader tie, we will eliminate both of them.  Thus, we conclude that Bush~Nader, so the societal preference pattern is Gore>Bush~Nader>Buchanan.  But this means that the societal preference pattern on the original three candidates (without the irrelevant alternative) is Bush~Nader>Buchanan, which is different from the original preference pattern.

Concept 5. Plurality

Consider the 1992 U.S. presidential election with three candidates, Clinton, Bush, and Perot.  The candidate who wins the election for that state is the candidate with the plurality of the votes.  In 1992, there were about 10.8 million residents of Ohio.  Assume about 40% of these residents voted in 1992, so assume that about 6 million people voted.  According to some numbers that I found on the web, the distribution of these votes were approximately as follows:

According to the total votes, Clinton clearly won the election.  However, suppose that Perot had not been running for office.  Popular opinion indicates that Perot took more votes from Bush than from Clinton, so let's assume that the distribution of votes without Perot in 1992 would mimic the distribution of votes between Dukakis and Bush in 1998.  Under these circumstances, the votes in 1992 would be approximately
 

Clearly, Bush would have won.  Although the data is only approximate and should not be blindly accepted, this example demonstrates that the plurality voting protocol is not independent of irrelevant alternatives.

Concept 6. Electoral College

Consider how the electoral college is influenced by the presence of an irrelevant alternative. In this case, agents are states rather than voters, and these electoral agents determine the president.  Consider again the 1992 U.S. presidential election with three candidates, Clinton, Bush, and Perot.  To simplify things, suppose that there are only four states and that each state has one electoral vote.  The preference pattern for these agent-states is determined by the plurality protocol.
 

Clinton wins 3 electoral votes to 1.  What happens when Perot drops out, supposing that all of the votes for him move to Bush?  Bush wins 3 electoral votes to 1.  Thus, the electoral college is not independent of irrelevant alternatives.
 

Concept 7. The Binary Protocol

Consider the following set of preferences.
 

Suppose that Larry controls the agenda and proposes that the first comparison is cherry to cream.  Since Larry and Moe both prefer cherry to cream, there are two votes for this preference pattern which means that society has cherry>cream.  Now, Larry proposes that the group decides which is preferred: cherry or apple.  Since Larry and Curly prefer apple, society has apple>cherry.  Whence, apple>cherry>cream.  Larry has controlled the outcome.

If you look closely, you'll see that if Curly had insisted that apple be compared to cream then society would have cream>apple.  The preferences are intransitive, and Larry has exploited this.

Suppose that Moe knew this about Larry.  He might say that he preferred cream to cherry.  Even with Larry's agenda, cream>cherry in the first round, and cream>apple in the second round.  Thus, Moe can enforce his second choice by lying about his preferences.

There are some interesting extensions of the binary protocol wherein all possible permutations of pairwise comparisons are made, and then the outcomes of these comparisons are accumulated.  If you are interested, I suggest looking at the web and in the library for information about these protocols.

The Mechanism Design Problem

Consider again the Borda voting protocol and suppose that the voters have the following preference patterns.

Under the Borda protocol, there is an incentive for Homer to lie about his true preferencesso that the societal preference pattern changes. To illustrate, suppose that instead of revealing his true preferences, Homer decides to say that Gore is his least favorite candidate.  This yields the preference profile below.

Notice how Homer's lie changed the ordering for society; Bush, who is Homer's favorite candidate, is now selected by the Borda protocol as the most preferred candidate.

This was well known to Borda.  Quoting Borda via the book The Theory of Incentives: The Principal-Agent Model by Laffont and Martimort (2002, Princeton University Press, page 15), "My scheme is only intended for honest men."  (Note that it is usually very bad form to not look up and then give the reference to the original text.  Unfortunately, the original text is a 1781 reference written in French.  I am therefore forced to quote a secondary source.)

Vickrey  elaborated on the problem with voting protocols in a 1960 article that deals with Arrow's impossibility theorem.  I'm again quoting from Laffont and Martimort, page 17 (this time because I'm working from home and don't have access to the library.)

There is another objection [in addition to them being "unfair"] to such welfare functions, however, which is that they are vulnerable to strategy.  By this is meant that individuals may be able to gain by reporting a preference differing from that which they actually hold."

Such a strategy could, of course, lead to a counterstrategy, and the process of arriving at a social decision could readily turn into a "game" in the technical sense.

Homer has an incentive to lie because doing so promotes Bush's ranking in society's choice.  Bart and Maggie, who like Bush least of all, can't cause their most preferred candidate Gore to increase in stature by lying about their preferences, but they can cause either Nader or Buchanan to receive the most points by promoting either one of these ahead of Gore.

The problem thus degenerates into a formal game in the way that we have defined it, where the actions available to the agents are the choices of what preference pattern they choose reveal.  For example, if Homer reveals his false preference pattern the Bart and Maggie both have an incentive to reveal their false preference patterns.  Clearly, there is a Nash equilibrium to this game, but does how fair is this Nash equilibrium solution.

Concept 2. What is mechanism design?

The problem of mechanism design is the problem of setting up the social choice function in such a way that there is a unique Nash equilibrium to the game and this equilibrium is "good" in some sense.  Quoting Hurwicz (via Laffont and Martimort, ,page 25),

In such a study, unlike in the more traditional approach, the mechanism becomes the unknown of the problem rather than a datum ... The members of such a domain (of mechanisms) can then be appraised in terms of their various "performance characteristics" and, in particular, of their (static and dynamic) optimality properties, their informational efficiency, and the compatability of their postulated behavior with self-interest (or other motivational variables).

 Note that Hurwicz's "performance characteristics" is a quest for some notion of "goodness."  One obvious good criterion is that we'd like people to reveal the truth about their preferences.  Unfortunately, Gibbard and Satterthwaite proved that "... with no prior knowledge of preferences, nondictatorial collectdive decision methods [that work for any type of profile] cannot be found where truthful behavior is a dominant strategy" (Laffont and Martimort, page 17).  In other words, there is no way to create a social choice mechanism that is both fair and that has a strategically dominant action the truthful revelation of preferences.

Mechanism design can be considered as a special case of two-agent decision-making.  In the figure, agent 1 is the mechanism designer and agent 2 is the group of all agents that will be required to make choices under the rules imposed by the mechanism designer.  For example, we can think of agent 1 as the founding fathers of the United States constitution and agent 2 as the citizens of the United States.  The job of agent 1, the founding fathers, is to create a social choice mechanism that translates agent 2's, the citizens, preferences into a choice for society.

The set of possible actions available to agent 1 is the set of possible mechanisms, and the set of possible actions available to agent 2 is the set of strategies (real or manipulated preferences).  The set of consequences is the set of choices made by society when they reveal their types and when agent 1 selects a mechanism design.  Agent 1's goals are to choose a consequence that minimizes the unfairness to society according to agent 1's perspective, and agent 2's goals are to reveal the type which produces a choice most closely aligned with their actual preferences.  The set of world states is the set of agent 2's true preferences.

You might be interested to know that the Gibbard-Satterthwaite impossibility theorem applies even if strength of preference is expressed via, for example, utilities.

Concept 3. Types

Occasionally, I have used the word type in the above discussion.  This terminology comes from the field of incentive design.  The background is that a principal (or boss) wants to hire an agent (or contractor or employee) to perform some task.  Unfortunately, there are multiple kinds of agents, some of whom are more effective at doing the task than others.  The principal wants to know which type of agent that is entering the contract, but the agent may not reveal the truth about themselves.  Simply put, an effective agent has no implicit incentive to reveal their true type because they can always pretend to be a less effective type of agent and thus try to get more payment for less work.

The word type is generalized to mean that the agent has some private information (in the case of the Borda protocol and Homer's preferences above, the private information is Homer's true preference pattern).  The agent may not truthfully reveal this private information, but instead reveal false information.  The true information is the type of agent, but the agent may pretend to be a different type (in the case of the Borda example, Homer pretends to be a type of agent that ranks Gore lowest in the priority scheme).  Thus, we say that an agent reveals a type.

Concept 4. Where Are We Going

Since there is no truth dominant fair mechanism for all social choice problems, what can we do?  We can either add an external incentive for agents to reveal their true preferences or we can restrict the problem domain so that we only pay attention to certain kinds of possible preference patterns (and ignore other kinds).  In the next lectures, we will study auctions in which the seller has to pay to get agents to reveal their true preferences (though the competition between bidders can sometimes make it possible for the seller to be able to pay as little as possible), and we will study the Clarke tax algorithm which has a provably truth dominant strategy when the agents have special kinds of preference patterns.