« Problems with Movable Type | Main | Marsh and McLennan Insurance Brokers: Common Agency »

November 12, 2004

Voting Cycles: A Game Theory Problem

I've just been inspired, on reading a draft chapter of Burt Monroe's Electoral Systems in Theory and Practice, to write up a long game theory problem for the next edition of Games and Information. It gets very technical, but I'll post it in case anybody might be interested.

Uno, Duo, and Tres are three people voting on whether the budget devoted to a project should be Increased, kept the Same, or Reduced. Their payoffs from the different outcomes, given below, are not monotonic in budget size. Uno thinks the project could be very profitable if its budget were increased, but will fail otherwise. Duo mildly wants a smaller budget. Tres likes the budget as it is now.


Uno Duo Tres

Increase 100 2 4
Same 3 6 9
Reduce 9 8 1

Each of the three voters writes down his first choice. If a policy gets a majority of the votes, it wins. Otherwise, Same is the chosen policy.


(a) Show that (Same, Same, Same) is a Nash equilibrium. Why does this equilibrium seem unreasonable to us?

... I continue to have severe Movable Type problems. I can't do Extended entries, so for more, go to Problem 4.7 in this page. When I've got time, I'll think about whether to switch weblog software.

November 14: Now maybe this will work:

ANSWER. The policy outcome is Same regardless of any one player's deviation. Thus, all three players are indifferent about their vote. This seems strange, though, because Uno is voting for his least-preferred alternative. Parts (c) and (d) formalize why this is implausible.

(b) Show that (Increase, Same, Same) is a Nash equilibrium.

ANSWER. The policy outcome is Same, but now only by a bare majority. If Uno deviates, his payoff remains 3, since he is not decisive. If Duo deviates to Increase,Increase wins and he reduces his payoff from 6 to 2; if Duo deviates to Reduce, each policy gets one vote and Same wins because of the tie, so his payoff remains 6. If Tres deviates to Increase, Increase wins and he reduces his payoff from 9 to 4; if Tres deviates to Reduce, each policy gets one vote and Same wins because of the tie, so his payoff remains 9.

(c) Show that if each player has an independent small probability epsilon of ``trembling'' and choosing each possible wrong action by mistake, (Same, Same, Same) and (Increase, Same, Same) are no longer equilibria.

ANSWER. Now there is positive probability that each player's vote is decisive. As a result, Uno deviates to Increase. Suppose Uno himself does not tremble. With probability epsilon (1-epsilon) Duo mistakenly chooses Increase while Tres chooses Same, in which case Uno's choice of Increase is decisive for Increase winning and will raise his payoff from 3 to 100. With the same probability, epsilon (1-epsilon), Tres mistakenly chooses Increase while Duo chooses Same. Again, Uno's choice of Increase is decisive for Increase winning. Thus, (Same, Same, Same) is no longer an equilibrium.

(With probability epsilon*epsilon, both Duo and Tres tremble and choose Increase by mistake. In that case, Uno's vote is not decisive; Increase wins even without his vote.)

How about (INCREASE, SAME, SAME)? First, note that a player cannot benefit by deviating to his least-preferred policy.

Could Uno benefit by deviating to Reduce, his second-preferred policy? No, because the probability of trembles that would make his vote for Reduce decisive is 2*epsilon (1-epsilon), as in the previous paragraph, and he would rather be decisive for Increase than for Reduce.

Could Duo benefit by deviating to Reduce, his most-preferred policy? If no other player trembles, that deviation would leave his payoff unchanged. If, however, one of the two other players trembles to Reduce and the other does not, which has probability 2*epsilon (1-epsilon). then Duo's voting for Reduce would be decisive and Reduce would win, raising Duo's payoff from 6 to 8. Thus, (Increase, Same, Same) is no longer an equilibrium.

Just for completeness, think about Tres's possible deviations. He has no reason to deviate from Same, since that is his most preferred policy. Reduce is his least-preferred policy, and if he deviates to Increase, Increase will win, in the absence of a tremble, and his payoff will fall from 9 to 4-- and since trembles have low probability, this reduction dominates any possibilities resulting from trembles.

(d) Show that (Reduce, Reduce, Same) is a Nash equilibrium that survives each player has an independent small probability epsilon of ``trembling'' and choosing each possible wrong action by mistake.


ANSWER. If Uno deviates to Increase or Same, the outcome will be Same and his payoff will fall from 9 to 3 If Duo deviates to Increase or Same, the outcome will be Same and his payoff will fall from 8 to 6. Tres's vote is not decisive, so his payoff will not change if he deviates. Thus, (Reduce, Reduce, Same) is a Nash equilibrium

How about trembles? The votes of both Uno and Duo are decisive in equilibrium, so if there are no trembles, they lose by deviating, and the probability of trembles is too small to make up for that. Tres is not decisive unless there is tremble. With probability 2*epsilon (1-epsilon) just one of the other players trembles and chooses Same, in which case Duo's vote for Same would be decisive; with probability 2*epsilon (1-epsilon) just one of the other players trembles and chooses Increase, in which case Duo's vote for Increase would be decisive. Since Tres's payoff from Same is bigger than his payoff from Increase, he will choose Same in the hopes of a tremble.

(e) Part (d) showed that if Uno and Duo are expected to choose Reduce, then Tres would choose Same if he could hope they might tremble-- not Increase. Suppose, instead, that Tres votes first, and publicly. Construct a subgame perfect equilibrium in which Tres chooses Increase. You need not worry about trembles now.

ANSWER. Tres's strategy is just an action, but Uno and Duo's strategies are actions conditional upon Tres's observed choice.

Tres: Increase
Uno: Increase|Increase;Reduce|Same, Reduce|Reduce
Duo: Reduce|Increase; Reduce|Same, Reduce|Reduce

Uno's equilibrium payoff is 100. If he deviated to Same|Increase and Tres chose Increase, his payoff would fall to 3; if he deviates to Reduce|Increase and Tres chose Increase, his payoff would fall to 9. Out of equilibrium, if Tres chose Same, Uno's payoff if he responds with Reduce is 9, but if he responds with Same it is 4. Out of equilibrium, if Tres chose Reduce, Uno's payoff is 9 regardless of his vote.

Duo's equilibrium payoff is 2. If Tres chooses Increase, Uno will choose Increase too and Duo's vote does not affect the outcome. If Tres chooses anything else, Uno will choose Reduce and Duo can achieve his most preferred outcome by choosing Reduce.

(f) Consider the following voting procedure. First, the three voters vote between Increase and Same. In the second round, they vote between the winning policy and Reduce. If, at that point, Increase is not the winning policy, the third vote is between Increase and whatever policy won in the second round.

What will happen? (watch out for the trick in this question!)

ANSWER. If the players are myopic, not looking ahead to future rounds, this is an illustration of the Condorcet paradox. In the first round, Same will beat Increase. In the second round, Reduce will beat Same. In the third round, Increase will be Reduce. The paradox is that the votes have cycled, and if we kept on holding votes, the process would never end.

The trick is that this procedure does not keep on going-- it only lasts three rounds. If the players look ahead, they will see that Increase will win if they behave myopically. That is fine with Uno, but Duo and Tres will look for a way out. They would both prefer Same to win. If the last round puts Same to a vote against Increase, Same will win. Thus, both Duo and Tres want Same to win the second round. In particular, Duo will {\it not} vote for Reduce in the second round, because he knows it would lose in the third round.

Rather, in the first round Duo and Tres will vote for Same against Increase; in the second round they will vote for Same against Reduce; and in the third round they will vote for Same against Increase again.

This is an example of how particular procedures make voting deterministic even if voting would cycle endlessly otherwise. It is a little bit like the T-period repeated game versus the infinitely repeated one; having a last round pins things down and lets the players find their optimal strategies by backwards induction.

Arrow's Impossibility Theorem says that social choice functions cannot be found that always reflect individual preferences and satisfy various other axioms. The axiom that fails in this example is that the procedure treat all policies symmetrically-- our voting procedure here prescribes a particular order for voting, and the outcome would be different under other orderings.


(g) Speculate about what would happen if the payoffs are in terms of dollar willingness to pay by each player and the players could make binding agreements to buy and sell votes. What, if anything, can you say about which policy would win, and what votes would be bought at what price?

ANSWER. Uno is willing to pay a lot more than the other two players to achieve his preferred outcome, He would be willing, to deviate from any equilibrium in which Increase would lose by offering to pay 20 for Duo's vote. Thus, we know Increase will win.

But Uno will not have to pay that much to get the vote. We have just shown that Increase will win. The only question is whether it is Duo or Tres that has his payoff increased by a vote payment from Uno. Duo and Tres are thus in a bidding war to sell their vote. Competition will drive the price down to zero! See Ramseyer & Rasmusen (1994).

This voting procedure, with vote purchases, also violates one of Arrow's Impossibility axioms-- his ``Independence of Irrelevant Alternatives'' rules out procedures that, like this one, rely on intensity of preferences.

Posted by erasmuse at November 12, 2004 03:06 AM

Trackback Pings

TrackBack URL for this entry:
http://www.rasmusen.org/mt-new/mt-tb.cgi/298

Listed below are links to weblogs that reference Voting Cycles: A Game Theory Problem:

» En lite längre länklista from hakank.blogg
Efter en längre tids lågbloggande krävs åter rengöring i Bloglines-tanken. För enkelhets skull har delar av informationstraverseringen lämnats ofullständig. Det kan här nämnas att vid slika lågbloggningstider tenderar aktiviteten på hakank's bloglines ... [Read More]

Tracked on November 13, 2004 10:09 AM

» En lite längre länklista from hakank.blogg
Efter en längre tids lågbloggande krävs åter rengöring i Bloglines-tanken. För enkelhets skull har delar av informationstraverseringen lämnats ofullständig. Det kan här nämnas att vid slika lågbloggningstider tenderar aktiviteten på hakank's bloglines ... [Read More]

Tracked on November 14, 2004 07:54 AM

Comments

Post a comment

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


Remember me?