Sébastien Courtin
email: sebastien.courtin@u-cergy.fr

Matías N Ú Ñez

Micael Castanheira

Amrita Dhillon

Ani Guerdjikova

A Map of Approval Voting Equilibria Outcomes *

Keywords: Approval voting, Condorcet winner, Voting equilibria, Asymmetric Societies JEL Classification D70, D72

It is commonly accepted that the multiplicity of equilibria is ubiquitous in preference aggregation games with any voting method. We prove that this multiplicity is greatly reduced under some mild restrictions over social preferences when each voter can vote for as many candidates as she wishes (the Approval voting method). For scenarios with three candidates, we can hence build a map that associates any preference profile to its set of equilibria outcomes; this map is very close to the most well-known Tournament solutions.

Introduction

Approval Voting (AV ) is the method of election according to which a voter can vote for as many candidates as she wishes, the elected candidate(s) being the one(s) who second feature of AV equilibria is the one presented in [START_REF] Laslier | Strategic Approval Voting in a Large Electorate[END_REF] which provides in a mass elections model3 a strong argument for the use of AV : in the absence of a tie in the expected scores of the candidates, AV uniquely selects the Condorcet Winner (CW ), the candidate that beats every other candidate in pairwise contests 4 .

However, the previous papers do not provide a full description of AV equilibria since the multiplicity of equilibria seems unavoidable. This paper proves that for a wide family of preference distributions, the asymmetric societies, this multiplicity of equilibria vanishes. This property of asymmetric societies allows us to draw a map of approval voting equilibria. A preference distribution is asymmetric if two conditions hold: the Simple Asymmetry (SA) and the Inverse Asymmetry (IA). According to SA, for any pair of candidates x, y the number of voters who prefer x to y must be different from the number of voters who prefer y to x. IA states that for any triple of candidates x, y, z, the number of voters who prefer x to y and y to z must be different from the number of voters who prefer z to y and y to x. Note that both conditions are very mild.

One main result emerges. On asymmetric large elections, AV produces two type of equilibria. In the former one, the Condorcet winner is the unique front-runner (i.e. he is the candidate with the highest expected score), whereas in the latter one, there are at least three candidates tied for victory. In other words, if there exists an equilibrium with a unique front-runner, then the front-runner must be the CW .

If the preference profile does not admit a Condorcet Winner, then there must be at least three candidates tied for victory. Moreover, we prove that if there exists a Condorcet winner then the game has an equilibrium in which he is elected.

Together, these results allows us to build a map (see Figure 1) that associates any preference profile to its set of voting equilibria outcomes in three candidate elections. This map is deeply related to the Tournament majority solutions such as the Top-Cycle set or the Bipartisan set. To build it, we combine equilibrium behavior and the approval relation (A) introduced by [START_REF] Courtin | Dominance Solvable Approval Voting Games[END_REF]. We say that a candidate x is A-preferred to a candidate y if the number of voters who rank x first and y last in their individual preference is higher than the number of voters who strictly prefer y to x minus the number of voters who rank y above x, none of them being either first or last. Note that with just three candidates, the definition of the relation is simpler since the number of voters who rank y above x, none of them being either first or last equals zero. A candidate y belongs to the Approval domain if there exists a candidate who is A-preferred to him.

Therefore there are three regions in this map. In region (i), the unique equilibrium of the game selects the CW as the front-runner of the election. In this region, the Approval domain is non-empty and hence a CW exists. In region (ii), while there exists a CW , the Approval domain is empty. In this region, there is always an equilibrium in which the CW wins but this equilibrium need not be unique (see Example 1). Finally, region (iii) simply stands for the preference distributions in which there is no CW . In this region, the unique equilibrium outcome distribution is a tie among all the candidates. In other words, in three candidates settings, the set of approval voting equilibria is close, even though, not equivalent to the Top-Cycle set (and hence to any other major tournament solution since they are equivalent with just three candidates).

Indeed, the Top-Cycle set stands for the set of candidates that are preferred to any other candidate via a chain of majority relations. In our setting, the Top-Cycle is equal either to the CW or the whole set of candidates in the absence of a CW .

This work is structured as follows. Section 2 introduces the general framework and Section 3 analyze AV outcomes on asymmetric societies. As far as the scenario with three candidates is concerned, the full description of AV equilibrium outcomes is included in Section 4 and Section 5 concludes the paper.

The electoral setting

The finite set of voters and candidates are respectively denoted by N = {1, . . . , n} and X = {a, b, . . . , k}. Note that n is supposed to be large. The strict preferences of a voter are defined by a von Neumann-Morgenstern (vN-M) utility function u : X → R, in which u(x) denotes the utility a voter gets if candidate x wins the election. In other words, for each i ∈ N and for any pair of candidates x, y ∈ X , x i y ⇐⇒ u i (x) > u i (y).

Voting

All voters vote simultaneously. Each voter can approve as many candidates as she wishes by choosing a ballot v = (v a , . . . , v k ) where v x ∈ {0, 1} denotes the number of points given to candidate x. With three candidates, the set of all possible ballots that a voter could submit under AV is V = (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (0, 0, 0), (1, 1, 1) .

An AV strategy is undominated if the voter approves her most preferred candidate and never approves of her worst preferred one. An AV strategy is sincere if, given the lowest-ranked candidate that a voter approves of, she also approves of all candidates ranked higher (see [START_REF] Brams | Approval Voting[END_REF] and [START_REF] Laslier | The Basic Approval Voting Game[END_REF]).

Society

Given the individual preferences, one can derive social preferences over pairs of candidates. For any pair of candidates x, y ∈ X , the majority relation M is defined as follows. We say that x is M-preferred to y, denoted xMy, if and only if

N (x, y) > N (y, x), with N (x, y) = #{i ∈ N | x i y}.
Throughout the work, we make two slight assumptions that ensure that social preferences are asymmetric. Note that both conditions are mild since they will generically hold if one considers for instance an odd number of voters.

SA: Simple Asymmetry. For any x, y ∈ X , N (x, y) N (y, x).

For any triple of candidates x, y, z ∈ X , we let N (x, y, z) denote the number of voters who prefer x to y and y to z; formally, N (x, y, z) = #{i ∈ N | x i y i z}.

IA: Inverse Asymmetry. For any triple of candidates x, y, z ∈ X , N (x, y, z) N (z, y, x).

The Condorcet Winner (CW ) is the candidate who is M-preferred to any other candidate in the election: x is the Condorcet Winner if and only if xMy for any y ∈ X \ {x}.

Consider a chain between candidates x and y which is a sequence of candidates Note that with three candidates, if both SA and IA hold, we have that either X T C = X if there is no Condorcet Winner or X T C = CW . With three candidates, the Top-Cycle set coincides with several tournament solution concepts such as the Uncovered set or the Bipartisan set (see [START_REF] Laslier | Tournament Solutions and Majority Voting[END_REF]). We just define the Top-Cycle as it is the simplest one of these concepts.

Approval relation

We now define the approval relation A. We say that candidate x is A-preferred to y if the number of voters who rank x first and y last (denoted N (x, . . . , y)) is higher than the number of voters who strictly prefer y to x plus the number of voters who prefer x to y but do not rank x first or y last (denoted N (•, x, y, •)). Formally, we have

xAy if and only if N (x, . . . , y) > N (y, x) + N (•, x, y, •).
Since with three candidates N (•, x, y, •) = 0 given that at least one of the two candidates is ranked first or last in a voter's preference ordering, it follows that xAy if and only if N (x, . . . , y) > N (y, x) when k = 3.

Note that the A relation is asymmetric and that A need not be complete.

The set X A (the Approval domain) stands for the candidates for which there exists a candidate who is A-preferred to them so that,

X A = {x ∈ X | ∃y s.t. yAx}.
[5] state among other things the following properties:

1. X A might be empty with X A X (α); 2. a candidate cannot win in any undominated strategy combination under AV if and only if it belongs to X A (β);

3. if #X A ≥ k -2, then the game has a CW (γ).

We now introduce a property of the A-relation that proves the existence of a link between Approval voting and the Tournament solutions. Indeed, any A-dominated candidate does not belong to the Top-cycle and to neither of its refinements.

Proposition 1. If k ∈ X A then k X T C .
Proof. Let X = {a, b, c, . . . , k} and k ∈ X A . We assume that aAk and that k ∈ X T C . If aMx ∀x a, then a is the CW so that k X T C , a contradiction.

Similarly, if yMk ∀y k, then k X T C , a contradiction. We hence assume that there exists some pair of candidates x and y with xMa and kMy.

Assume first that x = y which implies that xMa and kMx. However, Lemma 9 in [START_REF] Courtin | Dominance Solvable Approval Voting Games[END_REF] proves that for any triple a, b, c if aMb and bAc then aMc. In our case, we have xMa and aAk so that xMk, a contradiction with kMx.

Assume now that x y. W.l.o.g. we let x = b and y = c so that bMa and kMc.

1) bMa implies that N (a, b) < 1 2 .
The previous inequality can be rewritten as :

N (a, ..., k) + N (a, ., k, .) ≤ N (a, b) < 1 2 .
with N (a, ., k, .) the number of voters who rank a first and k not last.

2) aAk is equivalent to N (k, a) + N (., a, k, .) < N (a, ..., k).

3) If we combine (1) and (2), then

N (k, a) + N (., a, k, .) + N (a, ., k, .) < 1 2 .
4) kMc implies N (. . . , k) < 1 2 with N (. . . , k) the number of voters who rank k last. 5) Then if we add (3) and (4) we have

N (k, a) + N (., a, k, .) + N (a, ., k, .) + N (. . . , k) < 1. 6) Finally note that N (a, k) = N (., a, k, .) + N (a, ., k, .) + N (. . . , k) . But, by definition, N (k, a) + N (a, k) = 1 which is a contradiction with (5).

Large Elections

Let H be the set of all unordered pairs of candidates; a pair {x, y} in H is denoted by xy with xy = yx. The xy-pivot probability p xy is the probability (perceived by the voters) that candidates x and y are tied for first place in the election. A vector listing the pivot probabilities for all pairs of candidates is denoted by p = (p xy ) xy∈H . This vector p is assumed to be identical and common knowledge for all voters in the election. W.l.o.g. we let p represent a probability distribution so that xy∈H p xy = 1 with p xy ≥ 0.

A strategy is a probability distribution σ over the set V that describes the voting behavior of the voters. For any ballot v, σ i (v) equals the probability that voter i casts ballot v. The expected utility gain of a voter when she plays the strategy σ i (•) equals

U i (σ i (•); p).
Slightly abusing notation, we let U i (v; p) denote the expected utility gain of voter i from casting ballot v with:

U i (v; p) = xy∈H (v x -v y ) • p xy • [u i (x) -u i (y)]. (U )
Given the strategy combination σ, the share of the electorate who casts ballot v is denoted by

τ(v) = i∈N σ i (v). Hence, the expected score of candidate x is S(x) = v∈V v x τ(v).
The set of front runners of the election contains the candidates whose expected score S(x) is maximal given the strategy σ. MW impose the following consistency requirement in equilibrium: S(x) > S(y) =⇒ εp xz ≥ p yz , ∀ε ∈ (0, 1), ∀x, y, z. This implies that pivot probabilities involving candidates with low vote shares are zero in a similar fashion to the definition of proper equilibrium. We impose on beliefs a weaker version of MW's ordering condition. For any candidate x, let l be the unique leading candidate without x (if it exists): i.e. l = arg max y∈X \{x} S(y). We simply assume that εp xl ≥ p xz , ∀ε ∈ (0, 1), ∀x, z.

Our condition simply requires that the voters anticipate that the most likely pivot in which a candidate is involved is almost surely against the leading candidate. With three candidates, both conditions are quite close even though ours is substantially weaker with more candidates 5 . In order to see the main difference, take four candi- The probability of three (or more) candidates being tied for first place is infinitesimal in comparison to the probability of a two-candidate tie. Given a pivot probability vector p, the set of pure best replies of a voter equals

dates with S(x) > S(y) > S(z) > S(w) and consider the pivot probabilities in which

BR i (p) = {v ∈ V | v ∈ arg max v ∈V U i (v ; p)}.
Given the strategy σ i of a voter i, its support denotes the set of pure strategies played with positive probability according

to σ i : Supp(σ i ) = {v ∈ V | σ i (v) > 0}.
The strategy σ is a voting equilibrium of the game if and only if, for every positive number ε, there exists a vector p ε of positive pivot probabilities that satisfies the ordering condition for ε given σ, and such that, for each ballot v and for each voter

i ∈ N , if v ∈ Supp(σ i ), then v ∈ BR i (p ε ).
The set of equilibria is non-empty since our assumptions are weaker than those in MW which prove the existence of equilibrium.

Equilibria Outcomes in Asymmetric Societies

We now discuss the main implications of our work in scenarios with any number of candidates. The main characteristic of our results is that they do not depend explicitly on the voters' best responses. In other words, we do not need to completely define how the voters vote in order to predict how the equilibrium outcomes are.

The main logic is driven by the voters' anticipations to the possible scores of the candidates, greatly simplifying the task at hand. Proposition 2. If SA holds, then there is no AV equilibrium with two front-runners.

Proof. Assume, by contradiction, that there is an equilibrium with two front-runners. W.l.o.g. we let x and y be this pair of candidates. Due to the ordering condition, the most probable pivot outcome in which x (resp. y) is involved is against y (resp. x). Therefore, the voters who strictly prefer x over y vote for x and the ones who strictly prefer y over x vote for y. Hence, the score of x equals N (x, y) whereas the one of y equals N (y, x). However, since SA holds, the scores of such candidates must be different, contradicting the assumption that both x and y are tied. Proposition 3. If IA holds and there is an AV equilibrium with a unique front-runner, then this candidate must be the Condorcet Winner.

Proof. Assume that there is a unique front-runner in equilibrium, denoted a. Due to the ordering condition, every voter knows that, when ε → 0, the pivot outcome in which any candidate x a is involved against a becomes infinitely more likely than the rest of pivot events.

We have two cases: either there is a tie in the scores of two candidates (who are not the front-runners) or there is no tie.

Case 1: Assume first that, given σ, there is a tie in the expected score of two candidates who are not the front-runners. We denote them b and c w.l.o.g. As the most likely pivot outcome in which both are involved is against a, we know that the unique voters who vote for b (resp. c) are the ones who prefer b (resp. c) to a.

Therefore, the scores of both candidates are the following ones: Since the condition IA holds, it follows that the scores of b and c cannot be equal, a contradiction.

S(b) = N (b, a, c) + N (b, c, a) + N (c
In other words, when IA holds, there is not an equilibrium with a unique frontrunner in which two candidates are tied (in expected scores). So that, if there is a unique front-runner in equilibrium, the only possible case is that there is no tie in the expected score, to be analyzed in the Case 2.

Case 2: Assume now that there are no ties in the scores. Note first that N (x, a) N (y, a) for any pair x, y ∈ X . To prove this, it suffices to see that N (x, a) = N (x, a, y) + N (x, y, a) + N (y, x, a) and N (y, a) = N (y, a, x) + N (y, x, a) + N (x, y, a). The condition IA implies that N (x, a, y) N (y, a, x). Therefore, it must be the case that N (x, a) N (y, a) for any pair x, y ∈ X . W.l.o.g. we assume that N (b, a) > N (c, a) > . . . > N (k, a) ∀ b, c, . . . , k ∈ X .

Since every voter anticipates that the most likely pivot outcome involving any candidate x a is against a, it follows that the score of each candidate x a equals N (x, a) the share of voters who strictly prefer x to a whereas the one of a equals N (a, b). Hence, the scores of the candidates satisfy S(a) > S(b) > . . . > S(k). y = b, then N (b, a) > N (a, b) so that the score of b is higher than the score of a, a contradiction with a being the front-runner. If y b, then N (y, a) > 1/2 so that S(y) = N (y, a) > 1/2 > N (b, a) = S(b). Therefore, y is ranked second. In this case, the score of a equals N (a, y) < 1/2, a contradiction with a being the front-runner. Hence, it can only be the case that a is M-preferred to the rest of the candidates: for any x ∈ X \ {a}, aMx. In other words, it must be the case that a is the Condorcet winner.

Therefore, we can establish without proof the following corollary. Thus we have proved that there exists an equilibrium in which the CW is the unique front-runner, concluding the proof.

The Map

We now describe the main implications of the conditions of asymmetry on the shape of voting equilibria by constructing a map that associates any society to its set of front-runners in equilibrium in electoral situations with three candidates. The following example proves that some equilibria might exist only for certain utility levels of the voters, making more difficult the construction of the map.

Example 1: Let X = {a, b, c} and consider a society with the following proportions : 1 9 of the voters with u A = (10, µ, 0); 2 9 of the voters with u B = (10, 0, µ); 4 9 of the voters with u C = (10µ, 10, 0) and 2 9 of the voters with u D = (10µ, 0, 10). The candidate a is the CW and X A = ∅. Note that both SA and IA hold.

Since X A = ∅, property β implies that, for each candidate, there is a pure strategy combination under which the candidate wins with positive probability. However, due to SA and IA, some equilibria are removed.

Indeed, Proposition 2 implies that there is no equilibrium with two front-runners. Moreover, since there is a CW , Proposition 4 ensures that there exists an equilibrium in which a is the unique front-runner. Finally, there is no other equilibrium with a unique front-runner as ensured by Proposition 3. In other words, neither b or c can win alone.

One question remains to be answered: is there an equilibrium with the three candidates tied for victory? These equilibria might or not exist as a function of the voters' intensities of preferences. More formally, when 0 < µ < 5, there is no equilibrium with three front-runners (see Appendix A). Hence, in any equilibrium outcome, the CW is selected.

This example illustrates the fact that for a open set of utilities, when there is a CW and X A = ∅, the unique outcome AV might uniquely select the CW . However, for a different utility representation, we can find an equilibrium in which the three candidates get the same score. For example, if we set µ = 6, there is an equilibrium in which the three candidates are tied for victory as long as p ε = (5/8ε, 1/8ε, 2/8ε).

Building on Example 1, the following result describes the equilibria outcomes with three candidates and allows us to build the map in Figure 1. ii)If there is a Condorcet Winner with X A empty, there must exist an equilibrium in which he is the unique winner. The three candidates might be tied for victory.

iii) If there is no Condorcet Winner, the three candidates must be tied for victory. Proof. i) Since X A ∅ and k = 3, the property γ implies that there is a CW . Proposition 4 entails that if there is a CW in the profile, there must exist an equilibrium in which this candidate is the unique front-runner. As ensured by Proposition 2, there is no equilibrium with two front-runners. Moreover, there is no other equilibrium with a unique front-runner as ensured by Proposition 3. Therefore, the only type of equilibrium that might exist is the one in which the three candidates are tied. However, since X A ∅, property β ensures that some candidate is not in the set of front-runners for any undominated strategy combination. Hence, there is no equilibrium in which the three candidates are tied, proving the claim.

ii) Proposition 4 ensures that there exists an equilibrium in which the CW is the unique front-runner. Example 1 proves that there exists elections in which both situations might arise: either the CW is the unique candidate in the set of frontrunners or both equilibria are possible.

iii) This final point is a direct implication of Corollary 1.

Theorem 1 proves the existence of a deep link between the equilibria outcomes under AV and the theory of Tournament solutions. In a sense, AV almost implements the different solutions with just three candidates.

Concluding Comments

One of the main findings of this work is that in asymmetric societies, the Approval voting method leads to outcomes very close to the Top-Cycle set with three candidates. In other words, when voters are strategic, this rule gives incentives to voters to coordinate in a particular way: the equilibria outcomes (almost) coincide with the recommendations of the literature in Tournament solutions.

How does the map extend to more candidates? While at first one might think it is not the case, the answer is not completely straightforward. As shown by Proposition 1, the Approval Voting rule has a remarkable property: any A-dominated candidate does not belong to the Top-Cycle. Since the rest of Tournament solutions are refinements of the Top-Cycle, it follows that any A-dominated candidate cannot belong to any of them. A reasonable conjecture seems to be that for any preference profile, there must exist an equilibrium in which all the elements in the Top-Cycle or the Bipartisan set are tied for victory 6 . This equilibrium should exist independently of the utility levels of the voters. If either #X A ≥ k -3 or there is a CW , the conjecture holds whereas it is not so clear when the previous restrictions are not met.

Figure 1 :

 1 Figure 1: Top-cycle and the AV Equilibria Outcomes.

d 1 ,

 1 . . . , d m such that d 1 = x, d m = y, and not d l+1 Md l for each l = 1, . . . , m -1. Then the X T C = {x ∈ X | ∀y ∈ X , ∃ a chain between x and y}.

  , b, a), and S(c) = N (c, a, b) + N (c, b, a) + N (b, c, a).

Corollary 1 .

 1 If IA holds and there is no Condorcet winner, the set of front-runners contains at least three candidates in equilibrium. Proposition 4. If IA holds and there is a Condorcet winner, then there must exist an AV equilibrium that uniquely selects this candidate. Proof. Take a society in which there is a CW (denoted a) and in which IA holds. Since IA holds, we can assume w.l.o.g. that N (b, a) > N (c, a) > . . . > N (k, a). Indeed, as shown in the proof of Proposition 3 (case 2), if IA holds, then N (x, a) N (y, a) ∀x, y ∈ X . Assume that the scores satisfy S(a) > S(b) > . . . > S(k). Due to the ordering condition, it follows that the most likely pivot in which a is involved is against b whereas the most likely pivot outcome in which any other candidate x is against a. Thus, the score of a equals N (a, b) whereas the score of x (x a) equals N (x, a). As a is the CW , it follows that N (a, b) > 1/2 and that N (x, a) < 1/2 for any x a. Finally, since N (b, a) > N (c, a) > . . . > N (k, a), the scores satisfy S(a) > S(b) > . . . > S(k) as wanted.

Theorem 1 .

 1 Let k = 3. If both SA and IA hold, the voting equilibria are as follows: i) If there is a Condorcet Winner with X A non-empty, then the Condorcet winner is the unique winner.

  x is involved. The MW condition implies that εp xy ≥ p xz and εp xz ≥ p xw . Ours simply implies that εp xy ≥ p xz , p xw without any implication over the ratio between p xz and p xw .

The reader can refer to[START_REF] Brams | Approval Voting, Condorcet's Principle and Runoff Elections[END_REF],[START_REF] Weber | Approval Voting[END_REF] and the recent handbook of approval voting ([START_REF] Laslier | The Basic Approval Voting Game[END_REF]).

The notion of sincerity under AV is not completely obvious since there is not a one-to-one correspondence between the set of ballots and the set of preference profiles. According to the main used one, an AV ballot is sincere if whenever a voter approves of a given candidate c, she also approves of any candidate preferred to c.

[START_REF] Brams | Approval Voting, Condorcet's Principle and Runoff Elections[END_REF] We do not attempt here to give a full review of the literature. There is also a literature in small elections which reaches the same conclusion concerning the multiplicity of equilibria under AV , while using very different methods. For instance, see[START_REF] Sinopoli | Sophisticated Vote and Equilibrium Refinements under Plurality Rule[END_REF] and[START_REF] Sinopoli | Approval voting: three examples[END_REF] and[START_REF] Sinopoli | Counterexamples on the Superiority of Approval vs Plurality[END_REF]

].[START_REF] Brams | Approval Voting[END_REF] Note that these results hinge on the ordering condition. Indeed,[START_REF] Myerson | Large Poisson Games[END_REF][START_REF] Myerson | Comparison of Scoring Rules in Poisson Voting Games[END_REF] develop the Poisson voting games, a formal game-theory model to analyze large elections. However,[START_REF] Úñez | Condorcet Consistency of Approval Voting: A Counter Example on Large Poisson Games[END_REF] proves that in these games the ordering condition is not satisfied which leads to the victory of a candidate who is not the Condorcet Winner under AV .

The ordering condition plays a central role in these mass election models (see[START_REF] Úñez | Approval Voting on Large Election Models[END_REF] for a review of this condition). Indeed,[START_REF] Laslier | Strategic Approval Voting in a Large Electorate[END_REF] proves that when this condition holds (for a large number of voters), there exists an equilibrium under AV that leads to the election of the CW . In Poisson games, this condition need not be verified ([START_REF] Úñez | Condorcet Consistency of Approval Voting: A Counter Example on Large Poisson Games[END_REF]) which leads to bad preference aggregation; so is the case if one focuses on classic equilibrium refinements such as perfection or Mertens' stability as proved by[START_REF] Sinopoli | Approval voting: three examples[END_REF][START_REF] Sinopoli | Counterexamples on the Superiority of Approval vs Plurality[END_REF].

See the recent contribution by[START_REF] Kawai | Inferring Strategic Voting[END_REF] for a different weakening of the ordering condition in a related framework.

We would like to thank Jean-Franc ¸ois Laslier for the idea of the Bipartisan Set.

comments and encouragements. This work has also benefited from comments of several conference and seminar participants. This research has been developed within the center of excellence MME-DII (ANR-11-LBX-

A Appendix: Example 1

There is no equilibrium in this election in which the three candidates have the same expected score with no voter being indifferent between single and double voting. Indeed, when no voter is indifferent between single and double voting, it follows that all the voters with the same utility vector vote in the same way. One can check that in any possible combination of pure undominated strategies (each voter voting for her top candidate or for her two top candidates), there is no equality between the scores of the candidates. Hence, there is no such equilibrium with a three-way tie. Thus, in order to have such an outcome, some type of voters must be indifferent between single and double voting. In equilibrium, voters always approve of their most preferred candidate and never approve of their worst preferred one.

If just one type of voters play a mixed strategy, then it is not possible to obtain a three-way tie. If at least two types play in mixed strategies, then either C or D voters vote also for their middle ranked candidate so that a has the highest expected score. Indeed, assume first that a C voter plays a mixed strategy over her two undominated strategies so that U C (0, 1, 0) = U C (1, 1, 0). Due to (U ), the previous equality is equivalent to U C (1, 0, 0) = 0 so that

However, when ( * ) holds, we have that U D (1, 0, 1) > U D (0, 0, 1). To see why, note first that U D (1, 0, 1) > U D (0, 0, 1) ⇐⇒ U D (1, 0, 0) > 0. Moreover, remark that U D (1, 0, 0) = (10µ)p ε 12µp ε 13 so that, when ( * ) holds,

which holds since µ < 5.

Therefore, if a C voter plays a mixed strategy, D voters must vote for their second ranked candidate a, leading to its victory. A symmetric argument applies when a D voter plays a mixed strategy. Therefore, in any mixed strategy profile in which either C or D voters play a mixed strategy between their two undominated ballots, a is the sole winner of the election.

Hence, the only possibility for the existence of an equilibrium in which the three candidates get the same outcome is to assume that A and B voters both play a mixed strategy. However, this implies that

and U B (0, 0, 1) = 0 ⇐⇒ -p ε 13 (10µ) + p ε 23 µ = 0.

The previous two equalities imply that the unique pivot probability vector justifying such best responses equals p ε = (

10-µ 10+µ ε). However, as previously noted, U C (1, 0, 0) = p ε 13 (10-µ)-p ε 12 µ which is strictly positive given p ε since µ < 5. Hence, as in the previous case, if both A and B voters play a mixed strategy, C voters give one point to a, leading to its victory. Therefore, there is no equilibrium with three frontrunners. Moreover, by Proposition 4, we know that there must exist an equilibrium in which a is the unique front-runner. Furthermore, Proposition 2 implies that there is no equilibrium with two front-runners. Hence, in any equilibrium outcome, a is the unique front-runner as long as µ < 5.


Sébastien Courtin
email: sebastien.courtin@u-cergy.fr

Matías N Ú Ñez

Micael Castanheira

Amrita Dhillon

Dominance Solvable Approval Voting Games *

Keywords: Approval voting, Strategic voting, Dominance-solvability, Condorcet Winner JEL Classification Numbers: C72, D71, D72

This work provides necessary and sufficient conditions for the dominance solvability of approval voting games. Our conditions are very simple since they are based on the approval relation, a binary relation between the alternatives.

We distinguish between two sorts of dominance solvability and prove that the most stringent one leads to the election of the set of Condorcet Winners whereas this need not be the case for the weak version.

Introduction

What would be the outcome of an election if each voter was allowed to vote for as many candidates as she wanted rather than just for one as it is the case now? This is one of the main questions that the recent literature on voting theory has been concerned with, both in political science and economics. This idea of switching from 1 the "One man, One vote" principle (i.e. Plurality Voting) to the "One Man, Many Votes" one is indeed the focus of the theoretical debate over Approval Voting (AV) 1 . Our paper contributes this debate by considering the strategic analysis of the preference aggregation games. Rather than focusing on some normative criteria such as the Condorcet consistency 2 , we evaluate the merits of this rule by considering the equilibria of the following game. The voters' preferences are common knowledge and the voters play according to the Approval voting method: they can approve of as many candidates as they want. Voters are instrumental so that they only get utility from the outcome of the election. Ties are broken by a fair lottery.

As this game typically has (too) many equilibria, we focus on the situations in which most of the game-theoretical tools give a sharp and unique prediction. Indeed, we just consider which consider equilibria that survive to the iterated elimination of weakly dominated strategies (i.e. sophisticated voting à la Farquharson [START_REF] Farquharson | Theory of Voting[END_REF]). The games in which sophisticated voting leads to a unique outcome are dominancesolvable. Note that, as we consider generic games, this outcome satisfies a list of desiderata: this outcome is perfect and proper and moreover is the unique stable one à la Mertens [START_REF] Mertens | Stable Equilibria a Reformulation. Part i: Definition and Basic Properties[END_REF]. In a recent contribution, Buenrostro et al. [START_REF] Buenrostro | Scoring Rule Voting Games and Dominance Solvability[END_REF] underline the importance of the conditions for dominance solvability of approval games. They state some sufficient conditions for the solvability of scoring rule games and hence prove that whenever the conditions are satisfied for a scoring rule, so are the ones for AV . This is important since, whenever the conditions they describe hold, the outcome coincides with the set of Condorcet Winners and so, in a sense, these conditions are some sort of normative criteria for voting rules.

We distinguish two sorts of dominance solvability: cardinal (CS) and ordinal solvability (OS). Typically, the cardinal utilities of the voters are defined as the primitives of the game. Hence, for us, a game is CS if it is dominance solvable (i.e. there is some order of deletion that isolates a unique outcome). However, following the Arrovian tradition, one might consider that interpersonal comparable utilities should not be taken into account so that only the voters' ordinal preferences might have an impact on the outcome of the game. As will be shown, this need not be the case as the outcome by iterated removal of weakly dominated strategies might depend on the voters' cardinal preferences. In other words, given a ordinal preference ordering, different specifications of the utilities might have an impact on the prediction of dominance-solvability. Hence, we define a stronger notion of dominance solvability, OS, just based on the ordinal preferences. We say that a game is OS if every game with the same ordinal preference ordering is CS and the same outcome is reached. It follows that any OS game is CS whereas the contrary need not be true (see Example 1).

We answer two main questions: (i) when is a game OS and CS? and (ii) does the surviving outcome satisfy Condorcet Consistency?

As far as the first question is concerned, our answer is rather simple. Our conditions are based on the social preferences of the voters, and more precisely the approval relation (A) and the weak approval relation (ωA). We say that a candidate

x is (weakly) A-preferred to a candidate y if the number of voters who rank x first and y last in their individual preference is (weakly) higher than the number of voters who strictly prefer y to x minus the number of voters who rank y above x, none of them being either first or last. Note that with just three candidates, the definition of the relation is much simpler since the number of voters who rank y above x, none of them being either first or last equals zero. A candidate y belongs to the (weak) Approval domain if there exists a candidate who is A-preferred to him. We first prove that the A-relation fully characterizes the set of winners under AV provided that the voters use weakly undominated strategies. In other words, a candidate belongs to the Approval domain if and only if he cannot win the election since its maximal score is strictly lower than the minimal score of some other candidate.

Building on this result, we provide a characterization of dominance-solvability. With just three candidates, we first prove that if the Approval domain is nonempty, then the game is OS. Moreover, we show that if the Approval domain is empty but the weak Approval domain is non-empty, a game might be CS but not OS. Moreover, we prove that for such games, there is always a non-empty set of utilities for which the game is CS. In other words, the conditions for a game to be CS without being OS do not simply hinge on the number of the voters but also on their cardinal utilities. Finally, we prove that if the weak Approval domain is empty, then the game is not CS. Therefore, in a scenario with three alternatives, a game is OS if and only the Approval Domain is non-empty. More generally, if k candidates are present in the election, the requirements for OS are still based on the Approval Domain. If at least k -2 candidates belong to the Approval domain, the game is OS. Again, if the weak Approval domain is empty then the game cannot be CS. Note that if less than k -2 candidates belong to the Approval domain, the game need not be CS. Finally, it seems important to remark that our condition for OS implies the previous sufficient condition recently stated by Buenrostro et al. [START_REF] Buenrostro | Scoring Rule Voting Games and Dominance Solvability[END_REF]. Indeed, they prove that if the largest fraction of players that agree on the best or on the worst candidate is high enough, the game is CS.

Regarding the second question, we prove that the difference between OS and CS is key. Indeed, the literature was rather ambiguous on this precise point. On the one hand, Buenrostro et al. [START_REF] Buenrostro | Scoring Rule Voting Games and Dominance Solvability[END_REF] prove that under their sufficient conditions for dominance solvability, the set of Condorcet Winners was elected. On the other hand, the nice examples in De Sinopoli et al. [START_REF] Sinopoli | Approval voting: three examples[END_REF][START_REF] Sinopoli | Counterexamples on the superiority of approval vs plurality[END_REF] emphasize that this need not be the case. Our work gives a clear-cut answer to this controversy. We first prove that if a game is OS, then the outcome of dominance solvability equals the set of Condorcet Winners. On the contrary, if the game is CS but not OS it need not be the case that the outcome satisfies Condorcet Consistency. If one considers the whole set of CS games, this violation occurs under very precise conditions which can be stated with just three candidates as follows: it must be the case that the number of voters that rank some candidate x first and some candidate y must be equal to the number of voters who prefer y to x.

Intuitively, the main rationale behind the selection in Condorcet winners in OS games is as follows. In these games the procedure of dominance-solvability takes a very natural structure described by the following three steps:

1. Voters agree that every voter should only use weakly undominated strategies (voting for your top-candidate and never voting for your least-preferred one).

2. Given the previous agreement, at least k -2 candidates cannot be in the winning set since their maximal score is lower than the minimal score of some other candidate. Hence, it is irrelevant for the outcome of the election whether the voters vote for any of these candidates.

3. Finally, the majority winner among the (at most) two remaining candidates, wins the election.

Given that, when there is least k -2 candidates in the Approval domain there must exist a CW , the procedure of dominance-solvability correctly selects the CW . In games which are CS but not OS, the procedure does not follow the same steps since there are some candidates which maximal score coincides with the minimal score of some other candidates. This explains why a CS game fails to select the Condorcet winner.

The remainder of this paper is organized as follows. Section 2 introduces the model and defines concepts and notation that will be used in the rest of the article. As far as the scenario with three alternatives is concerned, Section 3 presents the sufficient conditions for an AV game to be OS and CS and Section 4 shows the necessary conditions. Finally, Section 5 discusses the Condorcet consistency, extends the results to the many alternatives case and concludes the paper.

Model

The voting game There is a set N = {1, ..., n} of voters with n ≥ 4 and a set X = {a, b, ..., k} of alternatives. With just three alternatives, we let X = {a, b, c}. The voting game is as follows. All voters vote simultaneously. A voter can approve as many candidates as she wishes by choosing a vector v i from the set of pure strategy vectors V i . With just three alternatives, we have:

V i = (1
, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (0, 0, 0), (1, 1, 1) .

The profile of vote vectors is

v ∈ V = i V i . The profile v -i ∈ V -i
denotes the vote profile excluding voter i. Let s j (v) be the number of votes for candidate j if the profile is v and s j (v -i ) the total score for candidate j when the vote of i is excluded. The vector s(v) = (s a (v), . . . , s k (v)) stands for the total score vector. s(v -i ) records the total votes for each candidate in X given a profile v -i ; we write s -i for short. The winning set of candidates, that is, the outcome corresponding to profile v, is denoted by W (v) and consists of those candidates that get the maximum total score:

W (v) = {x ∈ X | s x (v) = max y∈X s y (v)}.
Voter i ∈ N has strict preferences on the set of candidates X, which are strict orderings of X. a i b means that a is strictly preferred to b by voter i. The preference orderings of the voters are summarized by = ( i ) i∈N .

We assume that preferences can be represented by a von Neumann-Morgenstern (vN-M) utility function u i : X → R over lotteries on the set of candidates. Given that ties are broken by a fair lottery, the expected utility of a voter i is a function of the profile v given by :

U i (v) = 1 #W (v) x∈W (v) u i (x).
We will impose the following regularity condition (Dhillon and Lockwood [START_REF] Dhillon | When are plurality voting games dominance solvable?[END_REF]) to ensure that the order of deletion of weakly dominated strategies is irrelevant 3

: ∀i, v, v with W (v) W (v ) =⇒ U i (W (v)) U i (W (v )).
(

) 1
This condition implies that no voter is indifferent between any pair of candidates and moreover no voter is indifferent between any pair of winning sets.

Letting u = (u i ) i∈N , the strategic form voting game Γ is then defined by Γ = (u, V ). Given a preference ordering , we define the ordinal game as the class of games represented by the following set:

Γ = {Γ = (u, V ) | u is a vN-M representation of }.

Iterated weak dominance

Let ∅ V i ⊆ V i and V = i∈N V i be a restriction of V . Γ denotes the reduced game of V with strategy space V ⊆ V and winning set

W = {W (v) | v ∈ V } the restriction of W to V . Γ m , m = 1, 2, . . . denotes the sequence of reduced games of V with V m ⊆ V m-1 and W m denotes the restriction of W to V m . Let V 0 = V , lim m→∞ V m = V ∞ and lim m→∞ W m = W ∞ . Γ ∞ denotes the fully reduced game with Γ ∞ = (u, V ∞ ). Definition 1. A pure strategy v i ∈ V i very weakly dominates pure strategy ω i ∈ V i in Γ iff ∀v -i ∈ V -i , u i (v i , v -i ) ≥ u i (ω i , v -i ). v i weakly dominates pure strategy ω i in Γ iff v i very weakly dominates ω i in Γ and ∃v -i ∈ V -i such that u i (v i , v -i ) > u i (ω i , v -i ).
Fact 1: An AV strategy is not weakly dominated in V 0 if and only if the voter approves her most preferred candidate and never approves of her worst preferred one (see Brams and Fishburn [4]).

V ∞ stands for the full reduction of V through the sequence of restrictions V m in which there is no weakly dominated strategy.

A full reduction by pure weak dominance is achieved by maximal simultaneous deletion (msd) if at each step all the weakly dominated strategies of all players are deleted.

Definition 2. A pure strategy v i ∈ V is redundant in Γ = (u, V ) if there is some pure strategy ω i ∈ V such that u i (v i , v -i ) = u i (ω i , v -i ), ∀v -i ∈ V -i and ∀ i ∈ N .
We define two notions of dominance solvability. Definition 3. The game Γ = (u, V ) is cardinally solvable (CS) if there is a full reduction by pure weak dominance such that W ∞ is a singleton.

The outcome of a

CS game Γ = (u, V ) is denoted W ∞ Γ .
The first notion is a standard one in the literature. It just requires that a unique winning set is reached through one order of deletion of weakly dominated strategies.

Definition 4. Given a preference ordering , the game Γ is ordinally solvable (OS) if :

1. any game Γ in Γ is CS and 2. W ∞ Γ = W ∞ Γ for any pair Γ , Γ in Γ .
The second notion of dominance solvability is stronger. Indeed, as will be shown by the next example, the usual definition CS is not fully satisfactory in voting games since it does not simply hinge on the voters' ordinal utilities: it might lead to a different outcome as a function of the preferences' intensities of the voters. This second notion precludes this property of dominance solvability by requiring that the same outcome is reached in all the games that represent the same preference ordering.

Example 1: A non OS ordinal game.

Let n = 4 and X = {a, b, c} and consider the preference ordering given by

i = 1, 2 : a i b i c i = 3, 4 : c i b i a.
Due to Fact 1, the only weakly undominated strategies in V are {a} and {a, b} for i = 1, 2 and {c} and {c, b} for i = 3, 4. Take the game Γ 1 = (u, V 1 ) after one step of msd. Note that for any profile in this game, s a (v) = s c (v) = 2. Hence, any voter i with i = 1, 2 is indifferent between her two pure strategies when s -i ∈ {(1, 0, 2), (1, 3, 2)}. However, her decision when

s -i ∈ {(1, 1, 2), (1, 2, 2)} depends on her cardinal utility. If u i (b) < u i (a)+u i (c) 2
, she weakly prefers to vote {a}.

If u i (b) > u i (a)+u i (c) 2
, she weakly prefers to vote {a, b}.

A similar claim applies to a voter i

with i = 3, 4. If u i (b) < u i (a)+u i (c) 2
, she weakly prefers to vote {c}.

If u i (b) > u i (a)+u i (c) 2
, she weakly prefers to vote {b, c}. As we have assumed that no voter is indifferent between two winning sets, it follows that each voter has a unique weakly undominated strategy in V 1 that depends on her cardinal utilities. Therefore each game Γ in Γ is CS.

However, the outcome W ∞ Γ depends on the cardinal utilities. For instance, assume that u i (b)

< u i (a)+u i (c) 2 holds for every voter. Then W ∞ Γ ={a, c} . If, on the contrary, u i (b) > u i (a)+u i (c) 2
is satisfied for every voter, it follows that W ∞ Γ ={b} . Therefore, the ordinal game Γ is not OS since the outcome W ∞ Γ might differ across the different games in Γ .

The Approval Domain: a Sufficient Condition

Prior to stating the sufficient conditions for dominance solvability, we define some binary relations that will be necessary throughout.

We let N (x, y) denote the number of voters who prefer candidate x to candidate

y: N (x, y) = #{i ∈ N | x i y}.
x is M-preferred to y, denoted xMy, if and only if N (x, y) > N (y, x). The weak version of the relation M denoted x ωMy, is such that x ωMy if and only if N (x, y) ≥ N (y, x). The set of Condorcet Winners (CW ) are the candidate(s) who are preferred by a majority of voters to any other candidate in the election.

X CW = {x ∈ X|x ωMy ∀y x ∈ X}.
We now define the approval relation A. We say that candidate x is A-preferred to y if the number of voters who rank x first and y last is higher than the number of voters who strictly prefer y to x plus the number of voters who prefer x to y but do not rank x first or y last (denoted

N (•, x, y, •)). Formally, letting N (x, . . . , y) = #{i ∈ N | x i . . . i y}, xAy if and only if N (x, . . . , y) > N (y, x) + N (•, x, y, •).
Since with three alternatives N (•, x, y, •) = 0 given that at least one of the two candidates is ranked first or last in a voter's preference ordering, it follows that xAy if and only if N (x, . . . , y) > N (y, x) when k = 3.

Note that the A relation is asymmetric and that A need not be complete. Moreover, note that if xAy then xMy.

Indeed, if xAy then N (x, . . . , y) > N (y, x)+N (•, x, y, •). Given that N (x, y) ≥ N (x, . . . , y), it follows that N (x, y) > N (y, x) + N (•, x, y, •) ≥ N (y, x) ⇒ xMy.
The set X A (the Approval domain) stands for the candidates for which there exists a candidate who is A-preferred to them with

X A = {x ∈ X | ∃y s.t. yAx}.
Note that this set might be empty. Similarly the weak version of the relation A, denoted x ωAy, is such that x ωAy if and only if N (x, . . . , y) ≥ N (y, x) + N (•, x, y, •), and with associated set X ωA = {x ∈ X | ∃y s.t. y ωAx}.

We can state some simple claims concerning the properties of relation A.

Lemma 1. X A X.

Proof. Assume, by contradiction, that X A = X. Hence, for any candidate x, there exists a y for which yAx, so that N (y, . . . , x) > N (x, y) + N (•, y, x, •) (1). Since X A = X, there must exist a z with zAy which implies that N (z, . . . , y) > N (y, z)

+ N (•, z, y, •) (2).
However, note that N (x, y) ≥ N (z, . . . , y) as N (z, . . . , y) stands for the share of voters who rank z first and y last so that x is preferred to y in these profiles. Moreover, remark that N (y, z) ≥ N (y, . . . , x) by an analogous reasoning. Combining these two inequalities with (1) leads to the following inequality,

N (y, z) ≥ N (y, . . . , x) > N (x, y) + N (•, y, x, •) ≥ N (z, . . . , y) + N (•, y, x, •),
a contradiction with (2).

The following lemma will be useful throughout:

Lemma 2.
If the voters use weakly undominated strategies, then:

xAy ⇐⇒ s x (v) > s y (v) for any v.
Proof. Take a pair of alternatives x and y. Assume that s x (v) > s y (v) for any v when voters use weakly undominated strategies. This is equivalent to assume that the minimal score of x is higher than the maximal score of y (denoted s x > s y ). Under AV , it is weakly undominated for a voter to approve of her top preferred candidate and never vote her worst preferred one. Therefore, using weakly undominated strategies, the minimal score for a candidate x equals the number of voters who have x as their top-preferred candidate (denoted N (x, . . .)). Note that these voters can be divided between those who rank y last (N (x, . . . , y)) and those who do not (N (x, . . . , y c ), so that N (x, . . .) = N (x, . . . , y) + N (x, . . . , y c ).

Similarly, the maximal score of a candidate y equals the total number of voters minus the number of voters who rank this candidate last (n -N (. . . , y)). Again, all the voters who rank y over x (N (y, x)) are in this group. The rest of the voters in this group so are the ones who rank x over y without the voters who rank y last (N (x, y, •)) so that n -N (. . . , y)) = N (y, x) + N (x, y, •).

Hence, we can write that:

s x > s y ⇐⇒ N (x, • • • ) > n -N (• • • , y)) ⇐⇒ N (x, . . . , y) + N (x, . . . , y c ) > N (y, x) + N (x, y, •).
Removing the voters who rank x first and y not last from both sides of the inequality (in other words, N (x, . . . , y c ) = N (x, y, •)) leads to

s x > s y ⇐⇒ N (x, . . . , y) > N (y, x) + N (•, x, y, •).
Since this is the precise definition of xAy, this concludes the proof.

More formally, the previous lemma can be restated as follows:

y ∈ X A ⇐⇒ X W 1 for any X ⊆ Xwith y ∈ X . (2)
In other words, any set of candidates in which y ∈ X A is included can not be in the winning set W 1 , which corresponds to the possible winning sets in the game Γ 1 obtained after one step of msd. Our condition coincides with the one given by Brams and Sanver [START_REF] Brams | Critical Strategies under approval voting: Who gets ruled in and ruled out[END_REF] when k = 3. This is not surprising since they prove a characterization of a candidate being an AV winner, provided that the voters use sincere and undominated strategies (which is the case in our setting with just three alterrnatives).

The Approval Domain

Our analysis first focuses on a three candidates scenario which helps to present the main intuition for the many-alternatives case.

Voters' preferences are strict so that we divide the voters into six groups as follows:

N 1 N 2 N 3 N 4 N 5 N 6 a a b b c c b c a c a b c b c a b a n 1 n 2 n 3 n 4 n 5 n 6
with for example N 1 be the set of voters i with preference ordering a i b i c, with #N 1 = n 1 .

As condition (1) holds, we apply first one step of msd and so w.l.o.g. we focus on Γ 1 = (u, V 1 ) the game in which every voter chooses among her undominated strategies in Γ . As we focus on three candidates, each voter i has only two weakly undominated strategies under AV : either simple-voting for her top-ranked candidate (t i ) or double-voting for her first two top-ranked candidates (d i ). Note that W 1 is the winning set associated to Γ 1 with W 1 ∈ {{a} ; {b} ; {c} ; {a, b} ; {a, c} ; {b, c} ; {a, b, c}} .

Hence, the scores of the candidates under undominated AV voting strategies (i.e. any vote distribution in V 1 ) can be written for any vote distribution v as follows with

s a (v) = n 1 + n 2 + η 3 (v) + η 5 (v) s b (v) = n 3 + n 4 + η 1 (v) + η 6 (v) s c (v) = n 5 + n 6 + η 2 (v) + η 4 (v),
with η j (v) ∈ {0, . . . , n j } with j = 1, ..., 6. Note that for a given candidate the sum of the n j accounts for the votes he gets from simple-voting whereas the sum of η j stands for the votes which stem from double-voting. For a given Γ 1 the n j are constant whereas the η j depend on the vote profile.

We can now state a simple sufficient condition for an ordinal game to be OS.

Theorem 1. If X A ∅, then the ordinal game Γ is ordinally solvable.

Proof. Take a game Γ = (u, V ). After one step of msd, the set of winners in the game

Γ 1 = (u, V 1
) equals the set of AV winners under sincere and undominated strategies. If X A ∅, then there is some candidate which is not present in any winning set W 1 by ( 2). If two candidates are in X A , then there is a unique winning set that coincides with X \ X A . The claim is proved as then the game is CS, as wanted. Moreover, the argument does not hinge on the voters' cardinal utilities proving that the game is

OS.

If there is just one candidate in X A , then let X A = {c} w.l.o.g. Therefore W 1 = {{a}, {b}, {a, b}}. Any strategy that assigns one point to c is redundant to any strategy

v i ∈ V 1 that
assigns no point to it. We remove all the strategies in which voters assign one point to c as their second-ranked candidate 4 . Note that this has no impact of iterated removal of weakly dominated strategies due to condition [START_REF] Ahn | Approval Voting and Scoring Rules with Common Values[END_REF]. The game after removal of redundant strategies is denoted

Γ 2 = (u, V 2 ).
Consider two vote profiles v and v with v = (t i , v -i ) and v = (d i , v -i ). Note that the only difference between both profiles is that voter i switches from simple to double voting. Hence, as we are in Γ 2 , this change might only add one point to the voter's second ranked candidate, that is either a or b. The proof is now divided in two cases:

Case I. Suppose first that for some voter i, there exists v -i ∈ V 2 -i for which U i (v) U i (v ). Then it must be the case that W (v) W (v ). Consider first that a i b i c. As t i = (1, 0, 0) and d i = (1, 1, 0), switching from t i to d i adds one point to b. If W (v) = {a}, then it can only be the case that W (v ) = {a, b}. If W (v) = {b}, this is a contradiction since adding one point to b cannot change the winning set. If W (v) = {a, b}, then it follows that W (v ) = {b}. As voter i prefers a over b, she weakly prefers to choose t i .

The same argument applies to each possible preference ordering implying that no voter is indifferent between t i and d i so that the game is CS.

Case II. Suppose now that there is some voter i for which

U i (v) = U i (v ) for any v, v ∈ V 2 . Then it must be the case that W (v) = W (v ).
II.1 If W (v) is the same one for any v ∈ V 2 , then W 2 is a singleton so that the game is CS by definition.

II.2 Suppose now that there exist v

-i and v -i with W (t i , v -i ) = W (d i , v -i ), W (t i , v -i ) = W (d i , v -i ) and W (t i , v -i ) W (t i , v -i ).
Note that in Γ 2 , switching from t i to d i can only alter the score of a and b. A similar claim applies when

a. Assume first that W (t i , v -i ) = {a, b} for some v -i in V 2 -i . If a is the second-ranked candidate then W (t i , v -i ) = {a, b} =⇒ W (d i , v -i ) =
W (t i , v -i ) = {a, b}. b. Suppose now that W (t i , v -i ) {a, b} for any v -i in V 2 -i . If W (t i , v -i ) = {a} and W (t i , v -i ) = {b}, then s a (t i , v -i ) > s b (t i , v -i ) and s a (t i , v -i ) < s b (t i , v -i ).
By Lemma 7 in the appendix, there must exist some distribution v" -i with W (t i , v" -i ) = {a, b}. However, as previously, one can prove that there is a contradiction since adding an extra-point for a or b breaks the tie.

The same logic applies if

W (t i , v -i ) = {b} and W (t i , v -i ) = {a}.
In all the previous cases, either the game is DS or there is a contradiction, proving the claim. Finally, as the only driving force of the proof is the voters' ordinal preferences, we can conclude that the game Γ is OS.

Comparison to the previous sufficient conditions.

Buenrostro et al. [START_REF] Buenrostro | Scoring Rule Voting Games and Dominance Solvability[END_REF] provide sufficient conditions for the dominance solvability of AV games with just three candidates. Indeed, they focus on conditions in terms of one statistic of the game: sufficient agreement on the best candidate or on the worst candidate. We now prove that our condition (i.e. X A ∅) is strictly weaker than theirs. Indeed, any game satisfying conditions on the agreement on the best or on the worst candidate satisfy ours (Lemmata 3 and 4) whereas the contrary need not be true (Example 2).

We now summarize their two conditions and prove how they relate to ours.

Condition on the best candidate:

Their first condition states that if more than 2/3 of the voters have the same top-ranked candidate, the game is dominance solvable. So if a is this candidate, the condition can be written as follows:

If

n 1 + n 2 > 2 3
n, then the game is dominance solvable (CBest).

Lemma 3. If CBest holds, then X A ∅.

Proof. Take a game in which CBest holds for a so that n 1 + n 2 > 2 3 n. It follows that 6 i=3 n i < 1 3 n as 6 i=1 n i = n by definition. Moreover, it must be the case that either n 1 > 1 3 n or n 2 > 1 3 n in order to ensure that n 1 + n 2 > 2 3 n. Assume first that n 1 > 1 3 n. Then, n 1 > 1 3 n > 6 i=4 n i . However, n 1 = N (a, b, c) and 6 i=4 n i = N (c, a) so that the previous inequality is equivalent to N (a, b, c) > N (c, a). Therefore, aAc so that X A ∅ as wanted. A similar claim holds if n 2 > 1 3 n, finishing the proof.

Condition on the worst candidate:

Their second condition states that if more than 2/3 of the voters have the same worst-ranked candidate, the game is dominance solvable. So if c is this candidate, the condition can be written as follows:

If n 1 + n 3 > 2 3
n, then the game is dominance solvable. (CW orst) Lemma 4. If CW orst holds, then X A ∅.

Proof. Take a game in which CW orst holds for c so that n 1 + n 3 > 2 3 n. It follows that n 2 + n 4 + n 5 + n 6 < 1 3 n as 6 i=1 n i = n by definition. Moreover, it must be the case that either n 1 > 1 3 n or n 3 > 1 3 n in order to ensure that n 1 + n 3 > 2 3 n. Assume first that n 1 > 1 3 n. Then, n 1 > 1 3 n > n 4 + n 5 + n 6 , so that the previous inequality is equivalent to N (a, b, c) > N (c, a). Therefore, aAc so that X A ∅ as wanted. A similar claim holds if n 3 > 1 3 n, concluding the proof.

The next example proves that X A ∅ does not imply CBest and CW orst.

Example 2: X A ∅ need not imply neither CBest nor CW orst.

Let n = 5 and X = {a, b, c} and consider the preference ordering given by i = 1, 2, 3 :

a i b i c i = 4, 5 : c i b i a
This example is discussed by Buenrostro et al. [START_REF] Buenrostro | Scoring Rule Voting Games and Dominance Solvability[END_REF] in order to prove that their sufficient conditions are not necessary. Indeed, only 3/5 of the voters agree on the best and on the worst candidate and, nevertheless, the game is dominance solvable. Note that in this game, N (a, b, c) > N (c, a) so that X A ∅ proving that our sufficient condition for dominance solvability is weaker than theirs.

The weak Approval Domain: a Necessary Condition

In this section, we derive necessary condition for an ordinal game to be ordinally solvable with just three candidates. Indeed if the game is OS then the Approval domain can not be empty, as presented by the next result.

Theorem 2. If an ordinal game Γ is ordinally solvable, then X A ∅

The proof of this theorem is the purpose of this section. The three main steps of the proof are the following ones:

Step 1: Proposition 1 shows that if X ωA = ∅, then the game is not CS. Therefore if X ωA = ∅ for some game Γ , then the ordinal game Γ to which Γ belongs is not OS.

Step 2: Consider the games with X A = ∅ and X ωA ∅. These games might be CS (as shown in Example 1) but need not (see Example 3). Proposition 2 proves that none of these games is OS.

Step 3: Since the ordinal game is not OS when X ωA = ∅ or when X ωA ∅ and X A = ∅, it follows that if an ordinal game is OS then X A ∅. Proposition 1. If X ωA = ∅, then the game is not cardinally solvable.

Proof. Take a game with X ωA = ∅ (and hence X A = ∅). By definition, xωAy ⇐⇒

s x (v) ≥ s y (v) for any v ∈ V 1 .
As there is no candidate in the set X ωA , for any pair of candidates x and y, there exist two vote distributions v and v in V 1 with s x (v) > s y (v) and s x (v ) < s y (v ). Therefore, Lemma 7, included in the appendix, implies that all the winning sets are possible in V 1 .

We focus on the game Γ 1 after one step of msd. W.l.o.g. take a voter i with a i b i c so that t i = (1, 0, 0) and

d i = (1, 1, 0).
As all the winning sets are possible in V 1 , there must exist some

v -i ∈ V 1 -i for which either W (t i , v -i ) = {a, b} or W (d i , v -i ) = {a, b}. If W (t i , v -i ) = {a,
b} then as switching from t i to d i adds one point to b, then W (d i , v -i ) = {b}. Hence, given v -i , the voter i strictly prefers t i .

If W (d i , v -i ) = {a, b} then as switching from d i to t i removes one point to b, then W (t i , v -i ) = {a}. Hence, given v -i , the voter i strictly prefers t i .

Similarly, there must exist some

v -i ∈ V 1 -i for which either W (t i , v -i ) = {b, c} or W (d i , v -i ) = {b, c}. If W (t i , v -i ) = {b, c} then W (d i , v -i ) = {b}. Hence, given v -i , the voter i strictly prefers d i . Again, if W (d i , v -i ) = {b, c}, then W (t i , v -i ) = {c} so that the voter prefers d i .
Hence, the voter i has no weakly dominated strategy finishing the proof.

Example 3: X A = ∅ and X ωA ∅ need not imply that the game is CS.

As shown by Example 1, a game with X A = ∅ and X ωA ∅ might be cardinally solvable. To see that this type of games need not be CS take the following game. Let n = 5 and X = {a, b, c} and consider the preference ordering given by

i = 1, 2 : a i b i c i = 3 : a i c i b i = 4, 5 : c i b i a.
Note that aωAc as N (a, . . . , c) = N (c, a). Take first i = 1 and assume that u i = (3, 2, 0). If s -i = (2, 3, 2), then the voter prefers t i to

d i as U i (t i , v -i ) = 5/2 > U i (d i , v -i ) = 2. On the contrary, if s -i = (2, 3, 3), then the voter prefers d i to t i as U i (t i , v -i ) = 5/3 < U i (d i , v -i ) = 2.
The same reasoning applies to i = 2 proving that neither of these voters has a weakly dominated strategy in Γ 1 .

Take now i = 3 and assume that u i = (3, 0, 2). If s -i = (2, 2, 2), then the voter prefers t i to d i as U i (t i , v -i ) = 3 > U i (d i , v -i ) = 5/2. If we assume that s -i = (2, 3, 2), then the voter prefers d i to t i as U i (t i , v -i ) = 3/2 < U i (d i , v -i ) = 5/3. This proves that the voter 3 has no weakly undominated strategy.

Finally, take i = 4 with u i = (0, 1, 3). Note that when s -i = (3, 3, 1), then the voter prefers

d i to t i as U i (t i , v -i ) = 1/2 < U i (d i , v -i ) = 1. However, when the score s -i = (3, 3, 2), then it follows that U i (t i , v -i ) = 4/3 > U i (d i , v -i ) = 1
proving that this voter has no weakly undominated strategy in this game. The same claim applies to i = 5 by symmetry provided that she has the same utility profile.

Therefore, no voter has weakly dominated strategies after one step of msd proving that the game is not CS.

Note that in the game Γ 1 , the minimal score for a candidate x equals the number of voters who have x as their top-preferred candidate. Similarly, the maximal score of a candidate x equals the total number of voters minus the number of voters who rank this candidate last. Let us recall that s j and s j respectively denote min V 1 s j (v) and max V 1 s j (v).

Using the previous notation, the set of possible score vectors S = {s = (s j (v)) j∈X |v ∈

V 1 } can be characterized as follows:

s ∈ S ⇐⇒ s j (v) ∈ {s j , . . . , s j }.

While the sufficient condition (=⇒) holds by definition, the necessary condition (⇐=) is slightly more technical. Indeed, note under AV whether a voter approves of a candidate does not imply any restriction on the scores of the rest of the candidates (unlike under plurality voting). Hence it follows that any score for each possible candidate (between s j and s j ) is possible, independently of the scores of the rest of the candidates. In other words, for any possible vector s ∈ N 3 with s j ∈ {s j , . . . , s j } for any j ∈ X, we can find a vote profile v ∈ V 1 with s(v ) = s.

Building on the previous characterization, the next result describes which games can be dominance-solvable without being embedded in an ordinally-solvable ordinal game. As will be shown, these conditions are quite stringent. Proposition 2. If X A = ∅ and X ωA ∅ for some game Γ , then the ordinal game Γ to which Γ belongs is not OS.

Proof. Take a game with X A = ∅ and X ωA ∅.

We focus on the game Γ 1 after one step of msd. Assume w.l.o.g. that aωAc so that s a = s c as X A = ∅. Therefore if c is in the winning set so is a which implies that the possible winning sets are as follows:

W 1 ⊆ {{a}, {b}, {a, b}, {a, c}, {a, b, c}}.
Note that Lemma 8 ensures that {a, b, c} ∈ W 1 . The proof is now structured in three cases. The first two cases analyze the problem when {a, b} W 1 and when {a, c} W 1 . Finally, the third case focuses on the situation in which both {a, b} and {a, c} belong to W 1 .

Case I.

We assume in this case that there is not a vote profile v ∈ V 1 for which W (v) = {a, b}. Given that a ωAc, there are three cases: aωAb, bωAa or neither of both.

I.1 If aωAb, then s a = s b so that s a = s b = s c . As there is no v for which W (v) = {a, b}, then we must have s c = s c . Indeed, if s c < s c , by [START_REF] Brams | Approval voting in multicandidate elections[END_REF], there must exist a vector v

for which s a (v ) = s b (v ) > s c (v ), a contradiction.
As s c = s c , the candidate c is ranked either first or last by all voters since its minimal and maximal scores coincide. However, we have assumed that aωAb so that N (a, . . . , b) = N (b, a). Since no voter ranks c second, then N (a, . . . , b) = 0 so that N (b, a) = 0 in order to satisfy the equality. Hence, there are only two preference orderings a i b i c and c i a i b with the same number of voters (say m) for each ordering as aωAc. So the game has 2m voters with the voters i = 1, . . . , m with a i b i c and the voters i = m + 1, . . . , 2m with c i a i b.

Take a voter with preferences a i b i c. The only vote profile v -i in which she is not indifferent between voting t i = {a} and

d i = {a, b} is v -i = (m -1, m -1, m)
since in the rest either a wins alone or both a and c win.

If v -i = (m -1, m -1, m), then U i (t i , v -i ) > U i (d i , v -i ) ⇐⇒ u i (a)+u i (c) 2
> u i (b). By symmetry, the same reasoning applies to all the voters with these preferences.

Take now a voter with preferences c i a i b. For any utility representation, the voter strictly prefers to vote t i = {c} than d i = {c, a} when v -i equals (m, p, m -1) for any 0 ≤ p ≤ m -1. Similarly, she prefers to vote t i to d i when v -i = (m, m, m -1) iff

u i (c)+u i (b) 2
> u i (a). For the rest of the vote profiles, she is indifferent. The same applies for the voters with identical ordinal preferences.

Assume first that

u i (a)+u i (c) 2
> u i (b) for any i = 1, . . . , m and that

u i (c)+u i (b) 2
> u i (a) for any i = m + 1, . . . , 2m. Hence, the game is CS and the voters i = 1, . . . , m vote {a} whereas the rest of the voters vote {c}, implying that W ∞ = {a, c}.

Assume now that u i (a)+u i (c) 2

< u i (b) for any i = 1, . . . , m and that

u i (c)+u i (b) 2
< u i (a) for any i = m + 1, . . . , 2m. Hence, the voters i = 1, . . . , m vote {a, b} as {a} becomes a weakly dominated strategy whereas the rest of the voters do not have any weakly dominated strategy. After one new step of msd (i.e assuming that the voters i = 1, . . . , m vote {a, b}) then the voters i = m + 1, . . . , 2m vote {c, a} as it becomes weakly dominant.

Hence W ∞ = {a} since a gets a score of 2m whereas the rest of the candidates get a score of m.

This proves that the game cannot belong to an OS ordinal game since we have proved that W ∞ might depend on the utility levels of the voters.

I.2 If bωAa, then s b = s a so that s b = s a ≥ s a = s c as aωAc. It follows that s a = s a . Indeed, if s a > s a , then s b > s c which is equivalent bAc, a contradiction as X A = ∅. Moreover, as there is no v for which W (v) = {a, b}, then we must have s c = s c . Indeed, if s c < s c , by (3), there must exist a vector v for which

s a (v ) = s b (v ) > s c (v ), a contradiction.
Therefore, we have s b = s a = s a = s c = s c . As the minimal and maximal scores of both candidates a and c coincide, a and c can only be ranked either first or last. This implies that b is never ranked first so that s b = 0. However, in order to satisfy the inequality we must have that s a = s c = 0, a contradiction as by definition all voters always approve of their preferred candidate. I.3 Suppose finally that neither a ωAb nor b ωAa. Therefore, we have s a < s b and s b < s a . Hence, due to (4), it follows that s b ≤ s a < s b . Moreover, s a = s c as a ωAc.

First suppose that s b = s a . Notice that we must have s a = s c and s b < s a by assumption. Hence, combining the previous expressions, it follows that

s a = s c = s b < s a .
Hence, due to (3), there must exist some v for which W (v) = {a, b}, a contradiction. Now if s b < s a , there are two possibilities: either s a = s a or s a < s a . If the latter holds, then again by (3), there must exist some v for which W (v) = {a, b}, a contradiction. On the contrary, assume that s a = s a . Then a cannot be ranked second so that s a = s a = n 1 + n 2 and s c = n 2 + n 4 + n 6 . Since s a = s c as a ωAc, then n 1 + n 2 = n 2 + n 4 + n 6 so that n 1 = n 4 + n 6 . However, note that n 1 = n 4 + n 6 is equivalent to aωAb in this case, which does not hold by assumption. This concludes the case I.

Case II.

We assume in this case that there is not a vote profile v ∈ V 1 for which W (v) = {a, c}. Given that a ωAc, there are three cases: aωAb, bωAa or neither of both.

II.1 If aωAb, then s a = s b so that s a = s b = s c . As there is no v for which W (v) = {a, c}, then we must have s b = s b . Indeed, if s b < s b , by (3), there must exist a vector v for which s a (v ) = s c (v ) > s b (v ), a contradiction.

As s b = s b , the candidate b is ranked either first or last by all voters. However, we have assumed that aωAc so that N (a, . . . , c) = N (c, a). Since there is no voter without b ranked either first or last then N (a, . . . , c) = 0 so that N (c, a) = 0 in order to satisfy the equality. Hence, there are only two preference orderings a i c i b and b i a i c with the same number of voters (say m) for each ordering as aωAb.

The same argument as the one in case I.A proves that the game cannot belong to an OS ordinal game.

II.2

If bωAa, then s b = s a so that s b = s a ≥ s a = s c as aωAc. It follows that s a = s a . Indeed, if s a > s a , then s b > s c which is equivalent bAc, a contradiction as X A = ∅.

Therefore, we have s b = s a = s a = s c ≥ s c . As the minimal and maximal scores of candidate a coincides, a is ranked either first or last. Therefore, there only four possible preferences orderings a i b i c (n 1 voters), a i c i b (n 2 voters), b i c i a (n 4 voters) and c i b i a (n 6 voters). Since N (a, . . . , c) = N (c, a) it follows that n 1 = n 4 + n 6 . Similarly, as N (b, . . . , a) = N (a, b), we must have n 4 = n 1 + n 2 . However, both equalities together imply that n 1 = n 1 + n 2 + n 6 so that n 2 + n 6 = 0, which implies that both n 2 and n 6 equal zero. Hence there are only two preference orderings a i b i c (n 1 voters) and c i b i a (n 6 voters). Again, since aωAc, n 1 = n 6 = m. However, this game does not belong to an OS ordinal game since the only pivotal event involves the three-way tie (as in Example 1).

II.3

Suppose finally that neither a ωAb nor b ωAa. Therefore, we have s a < s b and s b < s a . Hence, due to (4), it follows that s b ≤ s a < s b . Moreover, s a = s c as a ωAc.

If s b < s a , then due to (3), there must exist a vote profile v for which W (v) = {a, c}, a contradiction.

If, on the contrary, s b = s a , then s c = s b = s a . Note that it must be the case that s a < s a . We must have {a, b} ∈ W 1 as otherwise there is a contradiction as proved by case I. As by assumption {a, c} W 1 , the voters in the groups N 2 and N 4 have always a weakly dominated strategy. Indeed, they are indifferent between t i and d i if the pivot event equals {a, b} as the only difference between both ballots is adding one point to candidate c. Moreover, if the pivot event involves the three candidates, they vote for d i if and only if

u i (a)+u i (b) 2
Hence, we can remove the strategies t i for both N 2 and N 4 voters which leads to the game Γ 2 = (u, V 2 ). Hence it must be the case that s c (v) = s c for any v ∈ V 2 . As s a = s b = s c , there must exist a v ∈ V 2 for which s a (v) = s b (v) = s c (v). Moreover, as s c < s a , s b , we must also have some v ∈ V 2 for which s a (v ) = s b (v ) > s c (v ).

Take a voter in the N 1 group with preferences a i b i c. She prefers t i to d i whenever W (t i , v -i ) = {a, b} or W (d i , v -i ) = {a, b}. Note that one of these two vote profiles must exist in V 2 . On the contrary, she prefers d i to t i when W (t i , v -i ) = {a, b, c} if and only if

u i (a)+u i (c) 2
< u i (b). Hence, this voter has no weakly dominated strategy. We assume that this is the case for all the voters in N 1 .

Moreover, for any i ∈ N 3 , we let

u i (b)+u i (c) 2
< u i (a). For any i ∈ N 5 , we let

u i (b)+u i (c) 2
> u i (a). For any i ∈ N 6 , we let

u i (a)+u i (c) 2
> u i (b). The previous inequalities imply that none of these voters have a weakly dominated strategy. This proves that the game Γ is not CS and hence the ordinal game Γ to which Γ belongs cannot be OS.

Case III.

We assume in this case that {{a, b}, {a, c}, {a, b, c}} ⊆ W 1 . Hence, all voters face an unambiguous pivot event which is independent of their utility levels (the two way ties) and an ambiguous one which involves the three way tie. Hence, for some utility level, each voter does not have a weakly dominated strategy, proving that the game cannot belong to an OS ordinal game.

For any preference ordering , let Γ be an ordinal game. The set U represents the set of cardinal utilities that represent .

Corollary 1. Let Γ be an ordinal game with X A = ∅ and X ωA ∅. Then there is a non-empty set of utilities Û ⊆ U for which any Γ = (V , u) with u ∈ Û is CS.

Proof. The proof of Theorem 2 analyzes the different games for which X A = ∅ and X ωA ∅. In each of the different cases, either the game does not exist or the game is CS for some utility levels proving the claim.

Concluding discussion

This section comments on the main remaining aspects of dominance solvability that have not been addressed so far: the extension of our results to a many-alternatives scenario and the Condorcet consistency of dominance solvability.

The general case

We now extend our results to the games with any number of candidates. The main difference is that it is not anymore the case that sincerity is weakly undominated. Hence, the voters might approve of some candidate without approving of a most preferred candidate. Theorem 3. If #X A ≥ k -2, then the ordinal game Γ is ordinally solvable.

Proof. Take a game Γ = (u, V ) with #X A ≥ k -2. After one step of msd, the set of winners in the game Γ 1 = (u, V 1 ) equals the set of AV winners under undominated strategies. Note that due to (2), any set of candidates which includes some candidate in X A does not belong to the winning set W 1 .

Since X A X (Lemma 1), there are just two cases.

If k -1 candidates are in X A , then the unique winning set corresponds to the victory of the unique candidate not present in X A proving that the game is CS.

If, on the contrary, there are k -2 candidates are in X A , then there are only two candidates (denoted x and y) who can win the election. Due to Lemma 7 (see the appendix), there must exist some vote profile v in which both x and y are tied. Moreover, this the only possible pivot event. Hence, since each voter has strict preferences over x and y, each voter approves of the one she prefers among both (and her top preferred alternative). Therefore, there is a unique winning set proving that the game is CS, as wanted. Moreover, the argument does not hinge on the voters' cardinal utilities proving that the game is OS. Theorem 4. If X ωA = ∅, then the game is not dominance solvable.

Proof. The proof is analogous to the one of Proposition 1. Indeed, since X ωA = ∅, there is a vote profile in which each candidate can win alone. Hence, due to Lemma 7 (see the appendix), for each pair of candidates x and y, there is a vote profile in which both candidates are tied. Moreover, due to (3), there must exist a vote profile in which both candidates are tied and with a score strictly above of the one corresponding to the rest of the candidates. Hence, no voter has a weakly undominated strategy since approving of a candidate might be pivotal against a most preferred candidate or a less preferred one. This proves that the game is not dominance solvable and concludes the proof.

We conjecture that if X A = ∅ and X ωA ∅, then the game cannot be OS but might be CS some non-empty set of utilities. In other words, Proposition 2 holds for any number of candidates. However, the proof seems to be technically challenging. Moreover, the boundary of the number of candidates in Theorem 3 is tight: that is, if #X A < k -2, the game need not be CS and hence the ordinal game in which it is embedded is not OS. To see why, consider the next example. We set u 1 = u 2 = (4, 3, 1, 0), u 3 = (4, 1, 3, 0) and u 4 = u 5 = (1, 2, 4, 0). In this game, X A = {d} so that #X A = 1 = k-3 < k-2. Moreover, after one step of msd, each voter can approve of each of their three preferred candidates. Note that all the possible strategy combinations depicted in the analysis of Example 3 are present in our game, whereas the contrary need not be true. Indeed, in our game the voters can approve of their three preferred candidates whereas in Example 3 they could only approve their two preferred candidates after one step of msd. Therefore, no voter has a weakly undominated strategy proving that the game is not CS as wanted.

Welfare Analysis

In Sections 3 and 4, a simple condition on the (weak) Approval domain is given in order to ensure OS. The next two lemmata (Lemma 5 and 6) prove that ordinally solvability satisfies Condorcet consistency. In other words, if a game is OS, then the outcome of dominance solvability equals the set of Condorcet Winners. To prove this claim, Lemma 5 proves that whenever the sufficient conditions for OS hold, then the voters' preference profile admits a CW . Building on this result, Lemma 6 proves it must be the Condorcet winner(s) that is to be selected by the procedure of dominance solvability.

We can also notice that (non-ordinal) solvability need not imply the selection of the CW as already proved by Example 1. Indeed, in this example, b might be the unique outcome whereas a and c are the CW . Lemma 5. If #X A ≥ k -2, then the game has a CW .

Proof. Take a game with #X A ≥ k -2. Note that as X A X (Lemma 1), there are only two possibilities: #X A = k -1 or #X A = k -2. Assume by contradiction that there is not a CW .

Assume first that #X A = k -2. W.l.o.g. we let X = {x 1 , x 2 , . . . , x k } and X A = {x 3 , . . . , x k }. It follows that for every x i with i = 3, . . . , k, there exists some x j ∈ X with x j Ax i . We denote the set of A-dominating candidates by X A = {x ∈ X|xAyfor somey ∈ X}. As previously stated, x j Ax i ⇐⇒ s j > s i . Take a candidate x j * with the maximal minimal score among the candidates in X A : formally,

x j * = arg max x j ∈X A s j .
Note that this candidate exists since there is a finite number of candidates in X A . Since s j * ≥ s j and s j > s i for any x j ∈ X A and any i = 3, . . . , k, it follows that s j * > s i , which is equivalent to x j * Ax i for any i = 3, . . . , k.

Assume that x j * ∈ {x 3 , . . . , x k }. Then, x j * Ax j * , a contradiction. Hence, x j * ∈ {x 1 , x 2 }. W.l.o.g we let x j * = x 1 . It follows that x 1 Ax i for any i = 3, . . . , k. If moreover x 1 Mx 2 , then x 1 is the CW , a contradiction. Assume, on the contrary, that x 2 ωMx 1 . Since

x 2 ωMx 1 and x 1 Ax i for any i = 3, . . . , k, Lemma 9 (included in the appendix) entails that x 2 Mx i for any i = 3, . . . , k. In other words, x 2 is the CW , a contradiction. A similar claim applies when #X A = k -1, finishing the proof. Lemma 6. If #X A ≥ k -2, then the outcome W ∞ is a CW .

Proof. Take a game with #X A ≥ k -2. Then the game is cardinally solvable as shown by Theorem 3. Moreover, the game admits a CW as proved by Lemma 5. The candidate which is in the outcome W ∞ is not in X A . Note that the CW cannot be in X A since every alternative in this set is M-dominated. If #X A = k -1, then there is a unique winning set after one step of msd. Hence, this candidate coincides with the CW of the election. If #X A = k -2, then assume w.l.o.g. X \ X A = {a, b} and aAc. By Theorem 1, the game is CS. Moreover, there are three possible winning sets {a},{b} and {a, b} after one step of msd.

Hence, all the voters approve of either a or b (the one they prefer) and they approve their most preferred candidate. Hence the winning set coincides with the set of CW . Indeed, if aMb, then a wins and conversely if bMa then b wins alone. Finally, if aωMb and bωMa then both candidates are weak CW and are tied for victory.

Note that with k = 3, this simply implies that if #X A ∅, then dominance solvability implies Condorcet consistency.

As a conclusion, the outcome of a dominance solvable game need not be a CW . This is a consequence of the game being CS but the ordinal game Γ in which the game is embedded not being OS. Therefore, if one considers the whole set of CS games, Condorcet consistency is violated when the weak Approval domain is non empty and the Approval domain is empty. However, when one focuses on the most stringent condition of dominance solvability, the surviving outcome must coincide with the set of CW . equality is equivalent to : N (z, x, y) + N (z, y, x) + N (y, z, x) > N (x, z, y) + N (x, y, z) + N (y, x, z). [START_REF] Ahn | Approval Voting and Scoring Rules with Common Values[END_REF] However, by assumption yAz, so that N (y, x, z) ≥ N (y, •, z) > N (z, y) ≥ N (z, x, y) + N (z, y, x) so that for (1) to hold, we need N (y, z, x) > N (x, y, z) + N (x, z, y) [START_REF] Bouton | One Person, Many Votes: Divided Majority and Information Aggregation[END_REF].

Moreover, we have assumed that xωMy so that N (x, y) ≥ N (y, x), which is equivalent to: N (x, y, z) + N (x, z, y) + N (z, x, y) ≥ N (y, x, z) + N (y, z, x) + N (z, y, x). (3) Again, as yAz, it follows that N (y, x, z) ≥ N (y, •, z) > N (z, y) ≥ N (x, z, y) + N (z, x, y). Hence, in order to ensure that (3) holds, we must have N (x, y, z) > N (y, z, x)+N (z, y, x) (4).

However, there is a contradiction between ( 2) and ( 4) proving the claim.

2. The proof of this claim is analogous to the one of 1. and hence is omitted.

  {a} entailing a contradiction. The same contradiction arises if b is the second-ranked candidate.

Example 4 :

 4 If #X A < k -2, then the game need not be CS. Consider the election depicted in Example 3 in which one extra-candidate is added at the bottom of the voters' preferences; this candidate is unanimously disliked. Let n = 5 and X = {a, b, c, d} and consider the preference ordering given by i = 1, 2 : a i b i c i d i = 3 : a i c i b i d i = 4, 5 : c i b i a i d.

A Condorcet Winner is a candidate that beats every other candidate in pair wises comparison. A rule is Condorcet consistent if it selects the Condorcet Winner whenever it exists.

It is irrelevant in the sense that two full reductions of a game through iterated weak dominance lead to the same winning set when condition 1 holds.

If we remove all the strategies that assign a score of 1 to c, we might modify the game as some voters vote for c and for some other candidate. Indeed, voters of groups N

and N

always assign one point to c and maybe one point to either a or b in Γ 1 . Hence, one cannot ensure that removing their strategies from the game does not affect the winning set since they might assign a positive score to both a and b.

and Jean-Franc ¸ois Laslier for their useful comments. This work has also benefited from comments of conference and seminar participants at the Cergy Micro Theory Group, the X-CREST Micro Seminar and at the

A Appendix: Proofs Lemma 7. Let k = 3. Let Γ 1 = (u, V 1 ). If there exists two vote profiles v and v for which s x (v) > s y (v) and s x (v ) < s y (v ), then there must exist a vote profile v" for which s x (v") = s y (v") Proof. W.l.o.g. we prove the claim for x = a and y = b. Denote by ∆(w) = s a (w) -

the difference between the scores of candidates a and b for any vote profile w. As (n 1 + n 2n 3n 4 ) is constant for a given game, it follows that ∆(w) can be rewritten as

Take two vote profiles v and v with ∆(v) > 0 and ∆(v ) < 0. It must be the case that cη 1η 6 < 0 and c + η 3 + η 5 > 0 in order to satisfy the definition of ∆(w). Therefore there must exist some vote distribution v" for which ∆(v") = 0, which concludes the proof. Lemma 8. If X A = ∅ and X ωA ∅, then there is some vote profile in V 1 for which the three candidates are tied, i.e. some v ∈

Proof. Take a game with X A = ∅ and X ωA ∅. Assume w.l.o.g. that c ∈ X ωA with a ωAc. Then, it follows that s a ≥ s c . Since X A = ∅, there does not exist a pair of candidates x, y with s x > s y . Hence, it must be the case that s a = s c .

Consider now the pair of candidates a and b. There are three possible cases: either a ωAb (Case I.), or b ωAa (Case II.) or finally that neither of the previous relations hold (Case III.).

Case I. Suppose first a ωAb which is equivalent to s a ≥ s b . Once again since X A = ∅, it must be the case s a = s b . Therefore, we have s a = s b = s c so that there exists a vote profile v with s a (v) = s b (v) = s c (v) as wanted.

Case II. Suppose now that b ωAa. This relation is equivalent to s b = s a as X A ∅. As s a = s c holds, we can write that s b = s a ≥ s a = s c since by definition s a ≥ s a . If s a = s a , then s b = s a = s c , so that there exists a vote profile for which the three candidates are tied. If, on the contrary, s a > s a , it follows that s b > s c so that aAc a contradiction with X A = ∅.

Case III. Suppose finally that neither aωAb nor bωAa. Then as X A = ∅, we can write that s a < s b and s b < s a .

Given that s a = s c , there must be the case that s b ≤ s a . Indeed, suppose that s b > s a . The previous inequality jointly with s a = s c implies that s b > s c implying that bAc, which contradicts X A = ∅.

Hence we have that

Let V be the set of vote distributions for which s a (v) = s c (v). Note that this set is non-empty as s a = s c . We assume that s a (v) = p. Due to (4), we know that p ∈ {s b , . . . , s b -1}. Moreover, due to (3), for any possible score vector s with s j ∈ {s j , . . . , s j }, we can find a vote profile v ∈ V 1 with s(v ) = s. Therefore, there exists a vote profile v ∈ V for which s a (v ) = s b (v ) = s c (v ) as wanted, concluding the proof. Lemma 9. For any triple of candidates x, y, z ∈ X:

1. if xωMy and yAz then xMz.

if xAy and yωMz then xMz.

Proof. 1. Take a triple of candidates x, y, z with xωMy and yAz.

Assume by contradiction that zMx so that N (z, x) > N (x, z). The previous in-