Soc Choice Welfare (2000) 17: 655±672

2000 9 9 9 9

Sophisticated voting and equilibrium re®nements under plurality rule Francesco De Sinopoli CORE, 34 Voie du Roman Pays, 1348 Louvain la Neuve, Belgium, (e-mail: [email protected]) Received: 16 March 1999/Accepted: 25 September 1999

Abstract. In this paper we show in the context of voting games with plurality rule that the ``perfect'' equilibrium concept does not appear restrictive enough, since, independently of preferences, it can exclude at most the election of only one candidate. Furthermore, some examples show that there are ``perfect'' equilibria that are not ``proper''. However, also some ``proper'' outcome is eliminated by sophisticated voting, while Mertens' stable set fully satis®es such criterium, for generic plurality games. Moreover, we highlight a weakness of the simple sophisticated voting principle. Finally, we ®nd that, for some games, sophisticated voting (and strategic stability) does not elect the Condorcet winner, neither it respects Duverger's law, even with a large number of voters. 1 Introduction An interesting application of strategic stability is o¨ered by voting games. As well known, the solution concept of Nash equilibrium has been proved to be too weak to fully capture strategic behavior of the players. Di¨erent solution concepts have been proposed to eliminate this weakness. However, all such solution concepts have been proven to be equivalent for generic normal form games. The peculiar aspect of a voting game is given by the fact that its normal form representation is highly non generic, as the same outcome arises An earlier version of this paper was circulated with the title ``Strategic stability and non cooperative voting games: the plurality rule''. I am deeply indebted to Jean-FrancËois Mertens for his encouragement, invaluable comments and suggestions in every step of the present research. I also thank Michel Le Breton and an anonymous referee for useful advice. Financial support from PAI P4/01 is gratefully acknowledge. The usual disclaimer applies.

656

F. De Sinopoli

from many di¨erent pure strategy combinations. More precisely, given the set of players N ˆ f1; . . . ; ng, the set of candidates K ˆ f1; . . . ; kg and the voting procedure …VP†, we have a game form. To obtain the associated non cooperative game we need the collection of utility vectors fu i gi A N , where u i ˆ …u1i ; . . . ; uki † and each uci represents the payo¨ that player i gets if candidate c is elected. In other words, the triplet …N; K; VP† de®nes a family of games, each game in this family is identi®ed with nk numbers; e.g. with plurality rule each voter has …k ‡ 1† pure strategies, therefore the corresponding normal form has n…k ‡ 1† n numbers. Hence results proven in the general class of normal form games have to be reconsidered in this context, since the voting procedure imposes constraints on the corresponding class of normal form games. In this paper we study the behavior of three solution concepts (``perfect'' equilibrium, ``proper'' equilibrium and Mertens' stable set) in the class of games de®ned by plurality rule and we relate them to the sophisticated voting principle. To do so, we apply the general model of a one stage voting procedure de®ned by Myerson and Weber [19] to the plurality rule case. Given the set of candidates K ˆ …1; . . . ; k†, each voter submits a ballot which is a vector of k components. An electoral system is then de®ned by the set of possible ballots that each voter can submit and by the election rule that, given the cast ballots, selects the winner from the set K. Hence, with the plurality rule every voter has the same strategy space and each pure strategy is a vector with all zeros except for a one in position c which represents the vote for candidate c. Abstention can be represented by the zero vector. With plurality, the election rule selects the candidate that receives the largest total number of votes. In case of ties, we allow an equal probability lottery among the winners. The importance of re®ning the Nash concept in voting games with plurality follows from the trivial observation that, in such games, even if every voter has the same preference order on the various alternatives, voting for the least preferred candidate is a Nash equilibrium if there are more than three voters. This follows from the main drawback of this concept, i.e. that it admits the use of (weakly) dominated strategies. We show that the solution concept of ``perfect'' equilibria, even if it guarantees admissibility, is not restrictive enough in this context, since it can exclude at most the election of only one candidate (a Condorcet loser), independently of the voters' preferences. Simple examples show that the ``proper'' equilibrium is a re®nement of the ``perfect'' concept, even for plurality games, but also that there are cases where some outcome selected by properness is eliminated by sophisticated voting and is not induced by any stable set. At this point it is important to stress that the di¨erent behavior of the various re®nements considered holds in complete neighborhoods, in the space of plurality games, of the proposed examples and hence these cannot be considered pathological. We show in [5] that, for generic utility vectors, the set of equilibria which induce a mixed distribution over the outcomes (i.e. with two or more candidates elected with positive probability) is ®nite and furthermore each of these is regular (in Harsanyi's sense). This result implies that, for generic plurality games, there are only ®nitely many equilibrium distributions and furthermore,

Sophisticated voting and stable sets

657

that all equilibria in the same stable set are outcome equivalent. From this we deduce that Mertens' stable sets, for generic plurality games, select the sophisticated outcome when it exists. However, sophisticated voting (and, hence, strategic stability) cannot explain Duverger's law [7], proved by Palfrey [21] under incomplete information, neither it leads to the election of a Condorcet winner. Furthermore, we will show how strategic stability is a stronger requirement than sophisticated voting. More precisely, we show that for an open set of plurality games, there is a candidate who is elected with probability one in a ``perfect'' equilibrium that survives the iterated elimination of dominated strategies, yet this outcome is not induced by any stable set of the game. This result follows from the fact that sophisticated voting simply requires the equilibrium strategies to survive the iterated deletion of dominated ones, but not that they conform to some ``good'' solution concept in the reduced game. It is possible to ®nd many applications of strategic stability, in the literature, mainly to signalling games or to multistage games where other concepts fail due to a lack of forward induction logic, while in plurality games the iterated dominance principle discriminates between the stable set and other solution concepts. Such principle has a long-standing tradition in voting theory since the pioneering work of Farquharson [8], who ®rst de®ned it ``sophisticated voting'', and has been the object of innumerable studies; among them it appears necessary to mention the work of Moulin [17] who based the de®nition of dominance solvable voting schemes on this criterium. Even if common voting procedures, such as plurality, are not dominance solvable, it appears sensible to require the solution to select the sophisticated outcome for the utility pro®les for which it exists. The results we present imply that such a simple requirement is not satis®ed, not even generically, by the ``perfect'' and the ``proper'' concepts, while stable sets fully satis®es it. 2 The plurality rule Given the set of candidates K ˆ …1; . . . ; k† and the set of voters N ˆ …1; . . . ; n†, the plurality rule determines the strategy space of each player. More precisely, since each voter can either cast his vote for each candidate or abstain, we have that the pure strategy set of each player i is: V i ˆ V ˆ f1; . . . ; k; 0g; where each c A K is a vector of k components with all zeros except for a one in position c which represents the vote for candidate c, while 0 is the zero vector representing abstention. Denoting K0 ˆ K W f0g, the strategy space of each player is: S ˆ D…K0 †: We do not need to know the ballots cast by all the voters in order to determine the winner, it is enough simply to know their sum. Given a

658

F. De Sinopoli

pure strategy vector v A V n , let o…v† ˆ

n P iˆ1

v i . Clearly o…v† is a vector with k

components, each one representing the total number of votes obtained by the corresponding candidate; then, denoting the probability that candidate c is elected if v is played by p…cjv†, and in order to simplify the notation, omitting the dependence of o from v, we have: 8 0 if bm A K s:t oc < om > > <1 if oc V om Em A K and : …1† p…cjv† ˆ q > > : afd A K s:t: oc ˆ od g ˆ q The set of candidates K, the set of voters N and the plurality rule de®ne a family of games; each game in this family is identi®ed by the utility vectors fu i gi A N , where u i ˆ …u1i ; . . . ; uki † and each uci represents the payo¨ that player i gets if candidate c is elected. Hence every plurality game with n voters and k candidates can be seen as point in < nk . For each pure strategy combination v, the payo¨ of player i is given by: X p…cjv†uci : …2† U i …v† ˆ cAK

Clearly we can extend (1) and (2) to mixed strategies. Under a mixed strategy s we have: X p…cjs† ˆ s…v† p…cjv† and U i …s† ˆ

X cAK

p…cjs†uci ;

where, as usual, s…v† denotes the probability of the (pure) strategy combination v under s. Since the election rule depends only upon the sum of the votes cast, the payo¨ functions and the best have this property. ( reply correspondence also ) P Then, de®ning W i ˆ $jbv i A V n 1 s:t: v j ˆ $ , we get the followj

ing de®nition of weak dominance, where …v i ; $† denotes every strategy combination in which player i votes for v and the behavior of the others is summarized by the vector $: De®nition 1. A ballot v weakly dominates, for player i, a ballot ^v, and we write vD i ^v, if: U i …v i ; $† V U i …^v i ; $† E$ A W U i …v i ; $† > U i …^v i ; $†

i

for some $:

…3†

A ballot v is said to be weakly dominant for player i if vD i v 0 for each v 0 A V nv. A ballot v is weakly dominated if there exists a strategy that dominates it.

Sophisticated voting and stable sets

659

We remark here that strongly dominant and strongly dominated strategies typically would not appear in plurality games, and henceforth we will omit the su½x weak when referring to relations in De®nition 1. In the following discussion, we will often refer to the next lemma: Lemma 2. In a plurality game where each player has a strict preference order over the set K, denoting Mi ˆ arg max uci , mi ˆ arg min uci , we have that: cAK

i

cAK

i

Mi D 0D mi

…4†

Furthermore with three voters and three candidates, denoting Li ˆ K i uLi i † V …uLi i umi i †: fmi g, if …uM i

fMi g

Mi D i Li i and if …uM i

uLi i † U …uLi i

umi i † then:

L i D i mi : Proof. We do not give a proof of the ®rst obvious and well known result here (cf. [3]). For the second part: with three candidates, every voter has the same strategy set V i ˆ f…1; 0; 0†; …0; 1; 0†; …0; 0; 1†; …0; 0; 0†g; then: W

i

 ˆ

 …0; 0; 0†; …1; 0; 0†; …0; 1; 0†; …0; 0; 1†; …2; 0; 0†; : …1; 1; 0†; …1; 0; 1†; …0; 2; 0†; …0; 1; 1†; …0; 0; 2†

Let us suppose (w.l.o.g.) that u1i > u2i > u3i . It is easy to see that voting for the ®rst candidate is a best reply for player i to every element of W i …0; 1; 1†, independently of the exact values of u i . It is trivial to see that: U i …1 i ; …0; 1; 1†† ˆ 13 …u1i ‡ u2i ‡ u3i † and U i …2 i ; …0; 1; 1†† ˆ u2i . With the fact that voting for the ®rst candidate is a strict best reply to …0; 0; 0†, simple algebra gives the ®rst result. Analogously it is easy to see that voting for the second candidate is always a better reply to W i …1; 1; 0† than voting for the third, independently of the exact values of u i and, furthermore, U i …2 i ; …1; 1; 0†† ˆ u2i and U i …3 i ; …1; 1; 0†† ˆ 13 …u1i ‡ u2i ‡ u3i †. Since, under the abstention of the other two voters, voting for the second candidate is strictly better than voting for the third, the last result follows. 9 Remark 3. Analogous results can be obtained for more than three candidates, but with more than three voters only the relations (4) will persist. 3 ``Perfect'' equilibria As mentioned above, even if every voter has the same preference order, voting for the least preferred candidate is a Nash equilibrium. This follows from the

660

F. De Sinopoli

main drawback of this solution concept, i.e. that it allows the use of dominated strategies. To avoid such irrational behavior, the concept of ``perfect'' equilibrium was introduced by Selten [22]. De®nition 4. A completely mixed strategy s e is an e-perfect equilibrium if Ei A N;

Ev i ; ^v i A V i

if U i …v i ; s e † > U i …^v i ; s e † then s e …^v i † U e: A strategy combination s is a perfect equilibrium if there exists a sequence fs e g of e-perfect equilibria converging (for e ! 0) to s. Since a perfect equilibrium does not contain dominated strategies, and voting for the least preferred candidates is dominated, such a concept eliminates the ``bad'' outcome described above. However, this solution concept does not appear su½ciently restrictive for plurality games since it excludes at most the election of only one candidate, independently of preferences. This is basically the result of the next proposition. Before stating it, we need the definition of a Condorcet loser: De®nition 5. A candidate c is a strict Condorcet loser if afi A N j c i c 0 g < afi A N j c 0 i cg Ec 0 A Knc:

…5†

A candidate c is a weak Condorcet loser if: afi A N j c i c 0 g U afi A N j c 0 i cg

Ec 0 A Knc:

…6†

Under the mild assumption that no voter is indi¨erent between two candidates, it is easy to show that if a candidate is not a strict Condorcet loser, a perfect equilibrium exists that leads to his election with positive probability, and furthermore if the candidate is not a weak Condorcet loser either, such probability is equal to one. Proposition 6. In a plurality game with more than 4 voters, if everyone has a strict preference order over the set K, then, for every candidate c A K who is not a strict Condorcet loser, there exists a perfect equilibrium s with p…cjs† V 12 . Furthermore, if c is not a weak Condorcet loser either, this probability is equal to 1. Proof. Take a candidate c who is not a Condorcet loser and let c 0 be the candidate for whom (5) (resp. (6)) does not hold. Divide the voters in two groups: N P …c; c 0 † ˆ fi A N j c i c 0 g N P …c; c 0 † ˆ fi A N j c 0 i cg: Consider the strategy combination s e where, for i A N P …c; c 0 †; sie ˆ …1

e

…k

1†e 3 †c ‡ ec 0 ‡ e 3 …0 ‡ 1 ‡


‡ k†:

Sophisticated voting and stable sets

661

and for i A N P …c; c 0 † sie ˆ …1

e

…k

1†e 3 †c 0 ‡ ec ‡ e 3 …0 ‡ 1 ‡


‡ k†:

It is obvious that, for e su½ciently close to zero, s e is an e-perfect equilibrium. In fact, for each voter the probability of being decisive between c and c 0 is in®nitely greater than the probability of any other circumstance where he is decisive. Hence, each voter uses in s e only his best reply with probability greater than e. Since, for e going to zero, the sequence fs e ge converges to the equilibrium where every voter who prefers c to c 0 votes for c, and every other votes for c 0 , we have the results. 9 The above proposition implies that the concept of ``perfect'' equilibrium is not very powerful in this class of games, since it excludes at most the election of only one candidate, independently of the voters' preferences. From this we deduce that some re®nement of the ``perfect'' concept has to be used to have more sensible solutions. 4 ``Proper'' equilibria We show in this section that, even in the class of plurality games, there are ``perfect'' equilibria that are not ``proper''. First of all, we review the de®nition of the ``proper'' concept introduced by Myerson [18]. De®nition 7. A completely mixed strategy s e is an e-proper equilibrium if Ei A N;

Ev i ; ^v i A V i

if U i …v i ; s e † > U i …^v i ; s e † then s e …^v i † U e
s e …v i †: A strategy combination s is a proper equilibrium if there exists a sequence fs e g of e-proper equilibria converging (for e ! 0) to s. If we compare the above de®nition with the de®nition of the ``perfect'' concept, it is evident that every proper equilibrium is also perfect, while the converse is not true. Furthermore, the constraints in the de®nition of e-proper equilibrium imply the impossibility to extend the proof of proposition 6 to the ``proper'' concept. The following example with three voters and three candidates shows that even in the class of plurality games, some perfect equilibrium outcome is not induced by proper equilibria. Moreover, this holds in a complete neighborhood, of this plurality game. Example I u 1 ˆ …3; 1; 0† u 2 ˆ …2; 3; 0† u 3 ˆ …2; 3; 0†:

662

F. De Sinopoli

For simplicity, let a denote the ®rst candidate, b the second and c the third. By lemma 2 we know that player 1 has a dominant strategy (a) while players 2 and 3 have two undominated strategies (a and b). The game has two undominated and perfect equilibria: a  ˆ …a; a; a† b  ˆ …a; b; b†; but only the second one is proper. To show that the equilibrium a  is perfect, it is enough to consider the following strategy combination s e : sie ˆ …1

e

2e 2 †a ‡ ec ‡ e 2 b ‡ e 2 0

Ei A N:

It is easy to see that for e su½ciently close to zero, this is an e-perfect equilibrium. In fact, for player 2 the probability (under …s1e ; s3e †) that candidates a and c receive one vote each is in®nitely greater than the probability of any other circumstance under which his vote matters. Hence voting for a is his best reply to …s1e ; s3e †. Analogously for the third player, while voting for a is dominant for player 1. Then s e is an e-perfect equilibrium. Since s e converges to a  for e going to zero, we have the perfection of this equilibrium. It is easy to see that a  is not proper. Suppose a  was a proper equilibrium. For convergence and dominance relationships, the strategies of players 2 and 3 in the sequence of e-proper equilibria converging to a  must then have the following form: sie ˆ d0 a ‡ d1 b ‡ d2 0 ‡ d3 c with dn‡1 U edn

i ˆ 2; 3:

As player 1 prefers, under …s2e ; s3e †, to vote for c than for b, his e-proper strategy has to be of the following form: s1e ˆ d0 a ‡ d1 0 ‡ d2 c ‡ d3 b

with dn‡1 U edn :

But it is easy to check that 2 and 3 prefer, for the above speci®ed strategies, voting for b than voting for a, hence a  cannot be a proper equilibrium. By existence of proper equilibrium (cf. [18]) we deduce than b  is the only proper, and hence perfect, equilibrium of the game. Moreover, the same result, i.e. that a  is perfect but only b  is proper, holds for every nearby game (in the space of plurality games). In fact, the same arguments apply to all games with the same preference order where u11

u21 > u21

u31

u22

u12 < u12

u32

u23

u13 < u13

u33 :

4.1 A drawback of the ``proper'' concept The main drawback of the ``proper'' concept in the context of voting games appears to be that it fails to satisfy the iterated dominance principle. Since the pioneering work of Farquharson [8] authors involved in voting theory have long used this principle (under the name of sophisticated voting) to solve these

Sophisticated voting and stable sets

663

kind of games (cf., among the others, [2], [14], [20]). Farquharson de®ned a strategy combination as sophisticated if it survives the iterated (simultaneous) elimination of dominated strategies. This requirement appears to be compelling. If we accept that rational agents do not use dominated strategies, it follows that these strategies should not a¨ect the strategic feature of the game. In other words, a solution concept based on individual rationality has to conform to sophisticated voting. Farquharson de®ned a voting game as ``determinate'' if sophisticated voting isolates an outcome. Even if most of plurality game are not determinate (i.e., plurality is not a dominance solvable voting scheme in the de®nition of [17]), it seems a weak requirement to ask the solution to select the ``sophisticated outcome'' when the plurality game is determinate (cf. also [11] for an in-depth discussion about this principle). The previous example is determinate and the sophisticated voting coincides with the unique proper equilibrium b  . In fact we know, by Lemma 2, that player 1 has a dominant strategy (a) while players 2 and 3 have two undominated ones (a and b). In the reduced game, obtained by eliminating all the other strategies, it is easy to see that b is dominant for players 2 and 3. However, the following example with three players and three candidates shows that the ``proper'' concept does not satisfy the ``sophisticated outcome'' principle in plurality games. Example II u 1 ˆ …0; 2; 3† u 2 ˆ …3; 2; 0† u 3 ˆ …3; 2; 0†: It is easy to calculate the set of undominated equilibria, which is given by the following two components: A ˆ …gb ‡ …1

g†c; a; a j 0 U g U 1†

B ˆ …gb ‡ …1

g†c; b; b j 0 U g U 1†:

To ®nd the proper equilibria we use Lemma 2, which implies the following dominance relationships: player 1 : cD0Da and bDa players 2 and 3 : aD0Dc and bDc: Since every proper equilibrium is undominated, we can proceed to analyze A and B. Consider the A component. Suppose a g  < 14 was a proper equilibrium. At equilibrium, for player 2 and 3, the strategy b is strictly better than 0, hence also nearby. This implies that the e-proper strategies of player 2 and 3 must have the following form: s e ˆ d0 a ‡ d1 b ‡ d2 0 ‡ d3 c with dn‡1 U edn :

664

F. De Sinopoli

But for these strategies of the last two voters, player 1 strictly prefers b to c, hence contradicting g  < 14 : It is possible to apply the same kind of argument to all g > 14. In this case the probability of player 2 and 3 trembling towards abstention is in®nitely greater than the one of trembling towards b. Hence player 1 prefers c to b, contradicting g > 14. Thus, the only proper equilibrium in A can be given by g ˆ 14. The following strategies show us that g ˆ 14 is in fact a proper equilibrium:   1 3 e 2 3 s1 ˆ …1 e e e † b ‡ c ‡ …1 y†eb ‡ yec ‡ e 2 0 ‡ e 3 a 4 4 s2e ˆ …1

e

e 2 †a ‡ …1

x†e0 ‡ xeb ‡ e 2 c

s3e ˆ …1

e

e 2 †a ‡ …1

x†e0 ‡ xeb ‡ e 2 c

with x ˆ

3 ‡ 8…e e 2 e 3 † 5 2e 8e 2

and

yˆ

11

2e 4…1 ‡ x†e 2 8 ‡ 4e 20e 2

…7† e4

:

The values of x and y assure that the strategies 0 and b are equivalent for player 2 and 3 along all the sequence, likewise the same is true for strategies b and c for player 1. Since every s e is an e 0 -proper equilibrium, we have   1 3  b ‡ c; a; a a ˆ 4 4 as a proper equilibrium. Let us now analyze the B component: for convergence and weak dominance, we get that in every e-proper equilibrium converging to B the strategies of players 2 and 3 have the following form: s e ˆ d0 b ‡ d1 a ‡ d2 0 ‡ d3 c with dn‡1 U edn which implies that strategy b gives player 1 a higher payo¨ than c. Hence, the only equilibrium in B that can be proper is the one corresponding to g ˆ 1. As a matter of fact, it is proper. It is easy to check that the following strategy is an e 0 -proper equilibrium: s1e ˆ …1

e

e2

e 3 †b ‡ ec ‡ e 2 0 ‡ e 3 a

s2e ˆ …1

e2

e3

e 4 †b ‡ e 2 a ‡ e 3 0 ‡ e 4 c

s2e ˆ …1

e2

e3

e 4 †b ‡ e 2 a ‡ e 3 0 ‡ e 4 c:

Hence, the game has two proper equilibria:   1 3  b ‡ c; a; a a ˆ 4 4 b  ˆ …b; b; b†: This game is determinate. By Lemma 2 we know that abstention and voting for the less preferred candidate is dominated for every player. Eliminating 0 and c for players 2 and 3, and 0 and a for player 1, we obtain a reduced

Sophisticated voting and stable sets

665

game where strategy c is dominated for player 1. Hence, eliminating this strategy too, a becomes dominant for the last two players. As a result, the game is determinate and the sophisticated outcome is the election of candidate a, while b is also elected in a proper equilibrium. Furthermore, the result of this example is robust. If the players have the above preference orders for all payo¨ vectors such that u31

u21 < u21

u11

u12

u22 < u22

u32

u13

u23 < u23

u33 ;

we obtain that the equilibrium b  ˆ …b; b; b† is proper, even if the sophisticated outcome coincides with the election of candidate a. We remark that the fact that there is at least one proper equilibrium that satis®es the sophisticated outcome principle is not strange at all. In the next section we derive some simple results that imply that, for almost all plurality games, the proper concept satis®es this weak version of the sophisticated voting principle as every stable set contains a proper equilibrium. 5 Stable sets In this section we focus our attention on Mertens' stable set. This formulation of stable set is preferred to the Kohlberg and Mertens' one [11], since the latter fails to satisfy the basic requirements of backwards induction and connectedness. We refer to [15] for the de®nition of Mertens' stable set and simply list here three of its properties (cf. [15]) we are going to use: i) Stable sets always exist. ii) Stable sets are connected sets of normal form perfect (hence undominated) equilibria. iii) A stable set contains a stable set of every game obtained by eliminating a strategy that is used with minimum probability in any e-perfect equilibrium close to it. These properties su½ce to fully characterize the solution of example II. In this example we know by (i) and (ii) that every stable set is contained in A or B. It follows by (iii) that every stable set contains a stable set of a game obtained by iterated elimination of dominated strategies. Hence the same argument made to claim that this game is determinate leads to the conclusion that every stable set is contained in A and it contains the equilibrium …b; a; a†. It is also clear that in any e-perfect equilibrium close to A, strategy a is the only best reply for 2 and 3. Hence b is used with minimum probability. Eliminating this strategy for 2 and 3, the strategy b becomes dominated for player 1. Hence from (iii) we deduce that the equilibrium …c; a; a† also has to be contained in every stable set; (ii) then implies that the game has a unique stable set S 1 A and the outcome induced by every element of the unique stable set coincides with the sophisticated one.

666

F. De Sinopoli

The fact that stability and sophisticated voting induce the same outcome when the game is determinate is not at all an exception. As a matter of fact, we will show that for almost all plurality games this is true. To prove this we have to introduce a result contained in ([5]). We remind that, given N and K, we have a family of plurality games and that this family can be identi®ed with < nk . As usual, we say that a given property holds for generic plurality games if, for every K and N, the closure of the subset in < nk for which it does not hold has Lebesgue measure zero. In ([5]) a strategy combination in which at least two candidates are elected with positive probability is called non-degenerate. The following theorem and its corollary are proven in [5]: Theorem 8. (De Sinopoli, 1999) For generic plurality games, the set of nondegenerate equilibria is ®nite and, furthermore, every non-degenerate equilibrium is regular. Corollary 9. (De Sinopoli, 1999) For generic plurality games, the set of equilibrium distributions over outcomes is ®nite. As well known, the elimination of weakly dominated strategies is orderdependent. The Farquharson's de®nition of sophisticated voting avoids this problem, imposing the simultaneous elimination of all the dominated strategies. We can drop this constraint and de®ning an outcome sophisticated*, if there exists at least one order of elimination of dominated strategies that isolates it. However, the above results imply that generically the sophisticated* outcome is unique (for analogous results, cf. also [9] and [13]) and, moreover, it is the only outcome induced by stable sets. In fact, we have: Proposition 10. For generic plurality games, (a) if the sophisticated* outcome exists, it is unique and, furthermore, it is the only stable one (i.e. the only outcome induced by elements of stable sets). (b) a non-degenerate equilibrium is a stable set. Proof. (a) Theorem 8 and property (ii) imply that all elements belonging to the same stable set are outcome equivalent. Moreover, property (iii) implies that every stable set contains a stable set of a game obtained by iterated elimination of dominated strategies, independently of the order. Thus, if the sophisticated* outcome exists, it is unique and is ``contained'' in every stable set. (b) Since we know that every regular equilibria ([10], [23]) is strongly stable ([12]) (cf. [23], Th.2.5.6), we need only to prove that strongly stability implies Mertens stability. This immediately follows from the fact that every perturbation of the strategies corresponds (continuously) to a perturbation of utilities; the continuity of the equilibrium function de®ning strong stability (cf. [23]) assures that the projection of its graph on the space of perturbed games is homologically non trivial, being a homeomorphism. For this point, see also [16] (pp. 697±699) who shows how the continuity of the map from the space of perturbed games to subsets of equilibria is a stronger requirement than the one included in the de®nition of stability. 9 If we are interested in ®nding the stable sets for (generic) plurality games,

Sophisticated voting and stable sets

667

proposition 10 (b) tell us that if there are some non-degenerate equilibria, they are also stable. We can then limit the analysis to those components of equilibria where a candidate is surely elected. Let us call them degenerate. At this stage of the analysis it is conceivable to think that, at least generically, degenerate stable sets are such that there is a ``®xed group'' of players who vote for the elected candidate and determine the outcome, whatever the other players will do. Unfortunately, such a conjecture turns out to be wrong, as the following example shows. Example III Consider the set of plurality games with three players and three candidates such that: 1 2

u 1 ˆ …1; a; 0†

0
u 2 ˆ …b; 1; 0†

1
u 3 ˆ …g; 0; 1†

1 < g < 1: 2

As above, let a, b, c denote, respectively, the ®rst, the second and the third candidate. We know by Lemma 2 that player 1 has a dominant strategy, voting for a, while the other two players have two undominated strategies (a and b for 2, a and c for 3). Once this point is acknowledged, it is straightforward to see that the set of undominated equilibria (ss) is: ss ˆ …a; a; xa ‡ …1

x†c j 0 U x U 1† W …a; ya ‡ …1

y†b; a j 0 U y U 1†:

We claim that these games have a unique Mertens' stable set that coincides with the set of undominated equilibria. Eliminating all the dominated strategies, we obtain a game between player 2 and player 3, where both players have voting for a as dominant strategy. Hence, by property (iii), every stable set contains the strategy where everybody votes for a (the sophisticated one). However, we can show that every stable set contains the extreme points of the set ss and hence, by property (ii), ss is the unique stable set of the game. To show that every stable set contains the point …a; a; c†, we consider a di¨erent order of elimination of dominated strategies. In fact, deleting b and 0 for player 1 and 3, we get a reduced game where voting for b and abstaining are, for player 2 dominated by voting for a. If we eliminate these two strategies of player 2, we have that c dominates a for player 3. Analogously, it can be shown that the point …a; b; a† is contained in every stable set.

668

F. De Sinopoli

Hence, the proposed conjecture does not hold for the considered set of plurality games. Since, up to a normalization, such a set corresponds to an open set in the class of plurality games with three voters and three candidates, thus the conjecture does not hold, not even generically. We underline that this example also shows how, even in the class of games we are dealing with, rationality's criteria, i.e. iterated elimination of dominated strategies, force the use of set-valued solution concepts and that, moreover, stronger equilibrium concepts than strategic stability, such as strict, regular and strongly stable equilibria, do not guarantee the existence of a solution, not even generically. We remark here that even in the benchmark example where every voter has the same preference order, the strict, the regular and the strongly stable equilibrium concepts have empty solution sets, with at least three voters. 5.1 On the weakness of sophisticated voting In this section we discuss an example where there is a candidate who is elected with probability one in a ``perfect'' equilibrium that survives the iterated elimination of dominated strategies, yet this outcome is not induced by any stable set of the game. More precisely, we show that even for open sets of plurality games there are perfect equilibria outcomes, that are not eliminated by sophisticated voting, yet these outcomes do not correspond to any perfect equilibrium of the reduced game, hence they are not induced by any stable set. In other words, strategic stability turns to be, for generic plurality games, a ``re®nement'' of sophisticated voting. The concept of sophisticated voting simply requires the strategy combination to survive the iterated elimination of dominated strategies. As remarked above, this requirement seems to be compelling. However, it appears to be too weak to fully capture strategic behaviour of the voters since it does not require the strategy combination to conform to some ``good'' solution concept in the reduced game obtained by eliminating dominated strategies. From the following example, we deduce that sophisticated voting cannot be considered a su½cient principle to determine ``strategically stable'' solutions, when it fails to select a unique outcome. Mertens' stability, satisfying well-funded game theoretic properties, is then preferable. Example IV u 1 ˆ …100; 99; 98; 0† u 2 ˆ …100; 99; 98; 0† u 3 ˆ …100; 99; 98; 0†

…8†

u 4 ˆ …2; 1; 0; 100†: It is not di½cult too see that …c; c; c; d† is a perfect equilibrium of this game, as in the proof of Proposition 6.

Sophisticated voting and stable sets

669

We know that every player has two (and only two) dominated strategies: abstention and voting for his worst candidates. Eliminating every player's ^ with the following pure dominated strategies, we obtain a reduced game …G† strategies sets: V^ 1 ˆ V^ 2 ˆ V^ 3 ˆ fa; b; cg V^ 4 ˆ fa; b; dg

…9†

^ Furthermore, G^ does It is easy to see that …c; c; c; d† is an equilibrium of G. not contain any dominated strategies. To show this, it is su½cient to see that for each strategy there is a strategy combination of the opponents such that it is the only best reply. Let us consider the ®rst player. It is clear that voting for a is the only best reply to s 1 ˆ …a; b; d†; voting for b is the only best reply to s 1 ˆ …c; b; d†, while voting for c is the only best reply to s 1 ˆ …c; 12 a ‡ 12 b; d†. Hence player 1 does not have a dominated strategy. Analogously for players 2 and 3. For the last player it is trivial to see that voting for a is the only best reply to s 4 ˆ …a; b; b†; voting for b is the only best reply to s 4 ˆ …b; c; c† and voting for d is the only best reply to s 4 ˆ …a; b; c†. Hence G^ does not contain any dominated strategies. The equilibrium …c; c; c; d† is then a perfect equilibrium of the game (8) and cannot be eliminated by sophisticated voting; furthermore, it leads to the election, with probability one, of the third candidate. ^ However, it is not di½cult to see that there is no perfect equilibrium of G, where the third candidate is elected with probability one. In order to show this, it is immediate to verify that …c; c; c; d† is the only Nash equilibrium of G^ where c is surely elected. In fact, if s is a Nash equilibrium of G^ such that p…cjs† ˆ 1, there are at least two players that vote for him with probability one. Let us assume that these are the ®rst and the second voter. If the third player does not vote for c with probability one, every best reply of 4 implies p…cjs† < 1. Viceversa, if player 4 does not vote for d with probability one, every best reply of player 3 implies p…cjs† < 1. Then …c; c; c; d† is the unique equilibrium of G^ where candidate c is surely elected, and it is undominated. However, such an equilibrium is not perfect. In fact, for every s e 4 converging to …c; c; c†, voting for d is not a best reply for the fourth player, since the probability of being either in o 4 ˆ …1; 0; 2; 0† or in o 4 ˆ …0; 1; 2; 0† is in®nitely greater than the probability of every other circumstance where player 4's vote matters. We remark here that the above results do not rely on the ``exact'' values of utilities and, hence, hold for every game su½ciently close to (8). We know that for (almost) all games close to (8), all equilibria in the same stable set are outcome equivalent. Hence, by properties (iii) and (ii), a necessary condition for c to be elected in a stable set is that there exists a perfect equilibrium of the reduced game G^ where he is elected with probability one. Since we have shown that no such a perfect equilibrium exists, we deduce that strategic

670

F. De Sinopoli

stability eliminates outcomes that survive sophisticated voting, also for open sets of plurality games. This example shows that sophisticated voting cannot be considered a suf®cient principle to determine solutions, when it fails to select a unique outcome. Strategic stability, satisfying well funded game theoretic properties, is then preferable. 5.2 On Condorcet winners and Duverger's law Since up to now the stable sets appears to be the ``right'' solution concept to study plurality games, two questions naturally arise. If there is a Condorcet winner (i.e. a candidate who defeats every other in a pairwise competition), does strategic stability force his election? Does strategic stability imply Duverger's law (i.e. only two candidates take a positive amount of votes), at least with a large number of voters? These two questions can have a strong formulation (i.e. in every stable set the properties are respected) or a weak one (i.e. at least a stable set with the above properties exists). However, the following example shows that the answers are both negative, even for the weak version. In fact, consider the case where there are three candidates (a, b and c) and three groups of n voters (A, B and C) with the following utilities: iAA

with u i ˆ …1; ai ; 0†

iAB

with u i ˆ …0; 1; bi †

iAC

with u i ˆ …0; gi ; 1†

0 < ai ; bi ; gi < 12

It is not di½cult to see, this is left to the reader, that the game is dominance solvable and, furthermore, sophisticated voting coincides with the strategy where each voters votes for his most preferred candidate. Since this strategy combination is a strict equilibrium, it is the only stable set of the game. Hence, in the unique stable set of the game the Duverger's law it is not respected and the Condorcet winner (b) is elected with probability 13, the same as the Condorcet loser (a). In an earlier version of this paper (cf. [4]) we showed that in a classical spatial model with three candidates sophisticated voting implies the election of the median voter's most preferred candidate, which is the only stable outcome, if there is a strong majority against one candidate (i.e. if a candidate is the least preferred for more than 23 of the voters). Hence strategic stability induces a ``median voter result'' without imposing a binary voting procedure. How this result can be extended when the game is not dominance solvable is an open problem, we hope that further research will lead to a deeper characterization, in plurality games, of the stable sets. E.g. it appears useful to ®nd a property that determines the solution of the spatial model with three candidates by only looking at the distribution of the voters.

Sophisticated voting and stable sets

671

6 Conclusion In this paper we have shown that in the context of voting games with plurality rule the ``perfect'' equilibrium concept is not restrictive enough since, independently of preferences, it excludes at most the election of only one candidate. We have shown that the ``proper'' concept is a re®nement of the ``perfect'' one, even for open sets of plurality games. However, this still presents some weakness. Even in this context there are ``proper'' outcomes that are not conform to the iterated dominance principle (sophisticated voting) while at least generically the stable set solution concept assures the sophisticated outcome, when it exists. Furthermore, we have shown that the simple sophisticated voting principle is too weak when it does not determine the outcome. More precisely, we have shown that for an open set of plurality games, there is a candidate who is elected with probability one in a ``perfect'' equilibrium which survives the iterated elimination of dominated strategy, yet this outcome is not induced by any stable set of the game. This follows from the weakness of the sophisticated voting principle which does not require the strategy combination to conform to an appropriate equilibrium concept in the reduced game. These considerations combined with the fact that stronger equilibrium concepts do not assure the existence of a solution for every plurality game, leads us to the conclusion that the Mertens' stable sets is the ``right'' solution concept to analyze plurality games. We have, moreover, given a ®rst attempt to characterize such a solution, showing how non-degenerate equilibria, generically, are stable. However, degenerate stable sets can be without a ``®xed group'' of players who vote for the elected candidates and determine the outcome, whatever the other players do. Finally we show that neither a weak Condorcet property nor Duverger's law necessary holds for stable sets (or for sophisticated voting). Furthermore it is possible to show, cf. [6], that the weakness of the ``perfect'' concept can lead to implausible outcomes, even in a model with endogenous candidacy such as the Besley and Coate's model [1]. All these considerations imply that stable sets deserve more attention in this class of games. It seems necessary to ®nd some properties that help us to characterize the solution without using their explicit de®nition. Another extension of the present work could be to study alternative voting procedures, e.g. Borda or approval.

References [1] Besley T, Coate S (1997) An economic model of representative democracy. Quart J Economics 112: 85±114 [2] Brams SJ (1975) Game theory and politics. Free Press, New York [3] Brams SJ (1994) Voting procedures. In: Aumann RJ, Hart S (eds) Handbook of game theory. Elsevier, Netherlands

672

F. De Sinopoli

[4] De Sinopoli F (1998). Strategic stability and non cooperative voting games: the plurality rule. CORE Discussion Paper 9843 [5] De Sinopoli F (1999) On the generic ®niteness of equilibrium outcomes in plurality games. Games Econ Beh (forthcoming) [6] De Sinopoli F, Turrini A (1999) A remark on voters' rationality in Besley and Coate model of representative democracy. CORE Discussion Paper 9927 [7] Duverger M (1954) Political parties. Methuen, London [8] Farquharson R (1969) Theory of voting. Yale University Press, New Haven [9] Gretlein RJ (1983) Dominance elimination procedure on ®nite alternative games. Int J Game Theory 12: 107±113 [10] Harsanyi JC (1973) Oddness of the number of equilibrium points: a new proof. Int J Game Theory 2: 235±250 [11] Kohlberg E, Mertens JF (1986) On the strategic stability of equilibria. Econometrica 54: 1003±1037 [12] Kojima M, Okada A, Shindoh S (1985) Strongly stable equilibrium points of nperson noncooperative games. Math Oper Res 10: 650±663 [13] Marx LM, Swinkels JM (1997) Order Independence for Iterated Weak Dominance. Games Econ Beh 18: 219±245 [14] McKelvey RD, Niemi RG (1978) A multi-stage game representation of sophisticated voting for binary procedures. J Econ Theory 18: 1±22 [15] Mertens JF (1989) Stable equilibria-A reformulation. Part I: De®nition and basic properties. Math Oper Res 14: 575±625 [16] Mertens JF (1991) Stable equilibria-A reformulation. Part II: Discussion of the de®nition, and further results. Math Oper Res 16: 694±773 [17] Moulin H (1979) Dominance solvable voting schemes. Econometrica 47: 1337± 1351 [18] Myerson RB (1978) Re®nements of the Nash equilibrium concept. Int J Game Theory 7: 73±80 [19] Myerson RB, Weber RJ (1993) A theory of voting equilibria. Amer Pol Sc Rev 87: 102±114 [20] Niemi RG, Frank AQ (1982) Sophisticated voting under the plurality procedure. In: Ordeshook PC, Shepsle KA (eds) Political equilibrium. Kluwer Nijho¨, Boston [21] Palfrey T (1989) A mathematical proof of Duverger's law. In: Ordeshook PC (ed) Models of strategic choice in politics. University of Michigan Press, Ann Arbor [22] Selten R (1975) Reexamination of the perfectness concept for equilibrium points in extensive games. Int J Game Theory 4: 24±55 [23] van Damme E (1991) Stability and perfection of Nash equilibria. 2nd ed, Springer, Berlin Heidelberg New York