Gibbard-Satterthwaite Games

1 Introduction

Voting is a common method of preference aggregation, which enables the participating agents to identify the best candidate given the individual agents' rankings of the candidates. However, a common concern of electoral designers is that no "reasonable" voting rule is immune to manipulation: as shown by Gibbard [1973] and Satterthwaite [1975], for three or more candidates, every onto, non-dictatorial voting rule admits a preference profile (a collection of voters' rankings) where some voter would be better off by submitting a ranking that differs from his truthful one. This cornerstone result is partially mitigated by the observation, developed in the last decade in the research area of computational social choice [Brandt et al., 2015], that voters will not necessary respond to an incentive of manipulation, in case such an action presents heavy computational costs.

An additional factor that may prevent strategic behavior in voters is that would-be manipulators must interact between themselves. The analysis of this interaction has been a very active area of research in political science, where several theoretical works have attempted to describe the micrologic behind strategic voting (e.g., [Cain, 1978; Cox, 1997; Myatt, 2007]). Most of these works concerns elections using the Plurality rule; for other voting rules the situation may be even more complex. On the one hand, some voters may not be able to manipulate on their own, but have an opportunity to take a defensive action which will destroy somebody's opportunity to manipulate. On the other hand, such countermanipulators are uncertain whether the manipulation, which they are going to counter, will take place or not. The voters in most elections are typically acting independently and in the absence of communication, hence strategic voters must play a simultaneous one-shot game in a non-cooperative setting. 1

Apart from the practical difficulties of manipulating, some voters may be ideological and interested in stating their preference no matter what. Practical observations suggest that the number of ideological voters is significant. For instance, in the famous Florida vote (2000), where Bush won over Gore by just 537 votes, 97,488 Nader supporters voted for Nader-even though in such a close election every strategic voter should have voted either for Gore or for Bush, and the overwhelming majority of Nader supporters preferred Gore to Bush. At the other end of the spectrum, truly strategic voters are interested in optimizing the outcome of the election and may or may not submit their insincere vote depending on strategic considerations. It is very hard to detect the number of strategic voters in a given election, but the percentage of those who actually manipulated may be easier to obtain. For instance, [Kawai and Watanabe, 2013] estimate the number of such voters in Japanese elections between 2,5% and 5,5%. Moreover, [Benjamin et al., 2013] show that preference misrepresentation is related to cognitive skills, and [Choi et al., 2014] demonstrate that decision-making ability in laboratory experiments correlates strongly with socio-economic status and wealth. Therefore, it is reasonable to assume that only a small fraction of voters in an election would act strategically when given an opportunity to do so.

The goal of our paper is to develop a basic understanding of how multiple manipulators can help or hurt each other by acting simultaneously, under some simple voting rules. In our model non-manipulators do not act strategically, since we assume that the strategic behavior of voters is prompted by the possibility of manipulating-see, however, our Example 7, where we show that countermanipulations can make the game much more complex. We model the interaction among the manipulators as a normal-form game, where the players - called GS-manipulators- are a subset of the manipulators in a given profile, each player's set of actions consists of her truthful vote and a subset of her manipulative votes, and players' preferences over action profiles are determined by who wins in the resulting elections (see Section 3 for formal definitions). We call such games the GS-games.

1 [Forsythe et al., 1993] found in laboratory that strategic voting is, indeed, more likely to occur if pre-election coordination devices such as polls and shared voting histories are available; in the model of [Myerson and Weber, 1993], which assume such coordination devices in the form of a common prior, the set of voting equilibria is always nonempty.

The paper is organized as follows. Section 2 presents some basic concepts of voting theory. In Section 3 we formally define the Gibbard-Satterthwaite games. Section 4 focuses on 2-by-2 games. Section 5 deals with computing weakly dominant strategies. Section 6 presents our results on the existence of Nash equilibria. Section 7 concludes. Some proofs are omitted due to space constraints.

RelatedWork There is a substantial body of research dating back to [Farquharson, 1969] that analyzes non-truthful voting as a strategic game; see, e.g., [Moulin, 1979; Myerson and Weber, 1993; Dhillon and Lockwood, 2004; Feddersen et al., 1990]. The algorithmic aspects of such models have recently received some attention as well [Desmedt and Elkind, 2010; Xia and Conitzer, 2010; Thompson et al., 2013; Obraztsova et al., 2013], with a strong focus on the problem of equilibrium selection. Indeed, a major difficulty in the study of general voting games is that they admit undesirable Nash equilibria such as, for instance, a situation in which all voters vote for the same candidate which none of them likes. Our analysis can also be seen from this perspective: by limiting the set of players, and restricting their action spaces, we eliminate counterintuitive behaviors.

Voting dynamics is a closely related topic, where players change their votes one by one in response to the current outcome [Meir et al., 2010; Lev and Rosenschein, 2012; Reijngoud and Endriss, 2012; Reyhaneh and Wilson, 2012; Obraztsova et al., 2015; Rabinovich et al., 2015]. With the exception of [Meir et al., 2010], in all of these papers the set of players consists of all voters, i.e., a player is allowed to vote non-truthfully even if he would be unable to manipulate the election on his own. Note that a convergence result in voting dynamics implies the existence of a Nash equilibrium in a GS-game, and indeed our Theorem 13 can be obtained as a consequence of a result by [Meir et al., 2010].

Our work can also be viewed as an extension of the model of safe strategic voting proposed by Slinko and White [2008; 2014]. However, unlike us, Slinko and White focus on a subset of GS-manipulators who (a) all have identical preferences and (b) choose between truthtelling and using a specific manipulative vote, and on the existence of weakly dominant nontruthful votes in this setting (such votes are called safe strategic votes). In contrast, we allow manipulators to have diverse preferences and to use strategy sets that contain more than one non-truthful vote.

2 Preliminaries

We consider n-voter elections over a candidate set C = {c1, . . . , cm}. An election is defined by a preference profile V = (v1, . . . , vn), where each vi, i = 1, . . . , n, is a total order over C; we refer to vi as the vote, or preferences, of voter i. For two candidates c1, c2 ∈ C we write c1 ≻i c2 if voter i ranks c1 above c2; if this is the case, we say that voter i prefers c1 to c2. For brevity we will sometimes write ab . . . z to represent a full ordering of the candidates vi with a ≻i b ≻i . . . ≻i z. We denote by topk(vi) the set of top k candidates in vi, and abbreviate top1(vi) to top(vi).

Given a preference profile V = (v1, . . . , vn), we denote by (V-i, v′i ) the preference profile obtained from V by replacing vi with v′i . Given two lists of candidates X = (x1, . . . , xℓ), Y = (y1, . . . , yℓ) we denote by v[X; Y ] the vote obtained by swapping xj with yj for j = 1, . . . , ℓ in vote v. If X and Y are singletons, i.e., X = (x), Y = (y), we omit the parentheses, and simply write v[x; y].

A voting rule is a mapping R that, given a profile V , outputs a candidate R(V ) ∈ C. We consider the following voting rules in this paper.

• k-approval, 1 ≤ k ≤ m- 1: under this rule, each candidate receives one point from each voter that ranks her in top k positions; 1-approval is also known as Plurality.
• Borda: under this rule, each candidate gets m-j points from each voter that ranks her in position j.

Under both rules, the score of a candidate is the total number of points she receives, and the winner is the candidate with the highest score. Ties are broken according to a fixed order > over C. We denote the k-approval score of c in a profile V by sck(c, V ), and c's Borda score in V by scB(c, V ).

We say that two votes v and v′ over the same candidate set C are equivalent with respect to a voting rule R if R(V-i, v) = R(V-i, v′ ) for every profile V . It is easy to see that v and v′ are equivalent with respect to k-approval if and only if topk(v) = topk(v′ ), and v and v′ are equivalent with respect to Borda if and only if v = v′ .

3 The Model

Our goal is to investigate strategic situations that arise when one or more voters could improve the outcome of the election from their perspective by unilaterally changing their votes. We will now define such situations formally.

Definition 1. We say that a voter i is a Gibbard-Satterthwaite manipulator, or a GS-manipulator, in a profile V = (v1, . . . , vn) with respect to a voting rule R if there exists a vote v′i ̸= vi such that i prefers R(V-i, v′i ) to R(V ). We denote the set of all GS-manipulators in a profile V with respect to a voting rule R by N(V,R). A vote v′i is called a GS-manipulation of voter i if i prefers R(V-i, v′i ) to R(V ), and, moreover, for every v′′ i it holds that either R(V-i, v′i ) = R(V-i, v′′ i ) or i prefers R(V-i, v′i ) to R(V-i, v′′ i ).

We say that i manipulates in favor of p by submitting a vote v′i ̸= vi if p is the winner in R(V-i, v′i ). Note that a voter can manipulate in favor of several different candidates; however, in the definition of a GS-manipulation we require the voter to focus on her most preferred candidate among the ones she can make the election winner.

Recall that a normal-form game is defined by a set of players N, and, for each i ∈ N, a set of actions Ai and a preference relation ⪰i defined on the space of action profiles, i.e., tuples of the form (a1, . . . , an), where ai ∈ Ai for all i ∈ N (while one could define normal-form games in terms of utility functions or in terms of preference relations, the latter approach is more suitable for our setting, as we only have ordinal information about the voters' preferences).

For each preference profile V and voting rule R, we consider a family of normal-form games defined as follows. Recall that N(V,R) is the set of GS-manipulators for V and R.

Definition 2. Given a preference profile V and a voting rule R, a GS-game for V and R is a normal-form game 〈N, {Ai}i∈N , {⪰i}i∈N 〉 where:

• N = N(V,R);
• for each player i, his set of actions Ai consists of his truthful vote and a subset of his GS-manipulations;
• the preference relation of player i is determined by the outcome of R on the preference profile that corresponds to a given action profile. Given an action profile V ∗ = (v∗ i )i∈N, let (V-N, V ∗ ) = (v′1 , . . . , v′n ) be the preference profile such that v′i = vi for i ̸∈ N and v′i = v∗ i for i ∈ N. Given two action profiles V ∗ and V ∗∗ , we write V ∗ ⪰i V ∗∗ if and only if player i prefers R(V-N, V ∗ ) to R(V-N , V ∗∗ ) or R(V-N , V ∗ ) = R(V-N , V ∗∗ ).

Observe that different choices of the actions sets Ai correspond to different games in the family. Denote the set of all GS-games for V and R by GS(V, R). All games in GS(V, R) have the same set of players, namely, N(V,R), so an individual game in GS(V,R) is fully determined by the players' sets of actions, i.e., (Ai)i∈N(V,R). Thus, in what follows, we write G = (V,R, (Ai)i∈N(V,R)); when V and R are clear from the context, we simply write G = (Ai)i∈N . We refer to an action profile in a GS-game as a GS-profile; we will sometimes identify the GS-profile V ∗ = (v∗ i )i∈N with the preference profile (V-N, V ∗ ). We denote the set of all GS-profiles in a game G by GSP(G).

Discussion. We emphasize a number of important features of this definition. First, we restrict the set of players to Gibbard-Satterthwaite manipulators. That is, we assume that, if a player cannot benefit from voting non-truthfully in the original profile, he will not be interested in exploring the possible benefits of strategic behavior when other voters manipulate as well. This attitude appears to be quite plausible: a voter may only be attracted to investigating the strategic aspects of the situation if manipulative behavior is profitable.

Second, we allow the players to limit themselves to subsets of their GS-manipulations, rather than consider a single game where each player's set of actions consists of his truthful vote and all of his GS-manipulations. There are several reasons for that. First, the space of all GS-manipulations for a given voter can be very large, and a player may be unable to identify all such votes. Second, the player may use a specific algorithm, such as that of Bartholdi et al. [1989], to find a GS-manipulation; in this case, her set of actions would consist of her truthful vote and the output of this algorithm. Third, the player may choose to ignore manipulations that are (weakly) dominated by others. Finally, a player may prefer not to change his vote beyond what is necessary to make his target candidate the election winner, because he does not enjoy lying [Obraztsova and Elkind, 2012], or fears unintended consequences of his actions in the complex environment of the game.

4 2-by-2 GS Games

In this section, we investigate which 2-by-2 games (i.e., games with two players and two actions per player) can be represented as GS-games. To address this question, we need a suitable classification of 2-by-2 games. Note first that every such game corresponds to 4 action profiles, and is fully described by giving both players' preferences over these profiles. By considering all possible pairs of preference relations over domains of size 4, Fraser and Kilgour [1986] show that there are 724 distinct 2-by-2 games.

However, this classification is too fine-grained for our purposes. Instead, we represent every 2-by-2 game by a diagram with 4 vertices and 4 directed edges, where an edge is directed from a less preferred profile to a more preferred profile (a bidirectional edge indicates indifference). For each player, let s denote his truthful vote and let i denote his manipulative vote; thus, the vertices of our diagram are (s, s), (i, s), (s, i), and (i, i). For two edges of this diagram their direction is determined by the fact that i is a GS-manipulation: namely, both of the edges adjacent to (s, s) are directed away from (s, s). Thus, by renaming the players if necessary, we can represent any 2-by-2 GS-game by one of the 6 diagrams in Figure 1. Observe that an action profile in a 2-by-2 game is a Nash equilibrium if and only if the corresponding vertex in the diagram of the game has two incoming edges. The following proposition is immediate from Figure 1.

Proposition 3. Every 2-by-2 GS-game has at least one Nash equilibrium in pure strategies.

Example 4. Consider the GS-game for the preference profile (abc, bac, cab, cba) under the Plurality voting rule, with ties broken according to a > b > c. In this game players 1 and 2 are the GS-manipulators; we can assume that their GSmanipulations are v∗ 1 = v1[a; b] and v∗ 2 = v2[b; a], respectively. Note that if both GS-manipulators vote insincerely, c remains the election winner. Thus, this game corresponds to diagram (ii) in Figure 1.

We say that diagram D is realizable by voting rule R if there exist a profile V and a 2-by-2 game G ∈ GS(V,R) such that D is the diagram for G. Our next goal is to study which diagrams are realizable by common voting rules.

Theorem 5. The only diagrams realizable by Plurality are (ii), (iii), (iv) and (v).

Proof. Consider a profile V , and assume that voters 1 and 2 are the GS-manipulators in V . Suppose that the Plurality winner in V is w, voter 1 manipulates in favor of a, and voter 2 manipulates in favor of b. Since voters 1 and 2 are GSmanipulators, we have w ̸= top(v1) and w ̸= top(v2). Thus, we can assume that their GS-manipulations are given by v∗ 1 = v1[top(v1); a], v∗ 2 = v2[top(v2); b]. Let V 1 = (V-1, v∗ 1 ), V 2 = (V-2, v∗ 2 ), V 12 = (v∗ 1 , v∗ 2 ). The winner in V 12 can be w, a, or b, and the case where it is w corresponds to diagram (ii). Further, if a = b, then a is the winner at V 1 , V 2 , and V 12 , corresponding to diagram (iii). Now, suppose that a ̸= b. As the winner at V 12 is either a or b, one of the arrows adjacent to (i, i) must be bidirectional, ruling out diagrams (i), (ii) and (vi) for this case. We have argued that diagrams (i) and (vi) are not realizable by Plurality. Example 4 realizes diagram (ii). We omit the examples for the remaining two cases due to lack of space.

Note that Theorem 5 implies that the Prisoner's dilemma is not realizable by Plurality. In contrast, for Borda all six diagrams are realizable.

Theorem 6. Diagrams (i)-(vi) are all realizable by Borda.

Proof. We provide an example for diagram (i), the remaining cases are omitted. Assume that ties are broken alphabetically. Let V = (dbcae, dbcae, acebd, acebd). The Borda winner in V is a. The first two voters are the GS-manipulators, and for each of them the vote v∗ = bdcea is a GS-manipulation in favor of c. Further, in (v∗ , v∗ , v3, v4) the Borda winner is b.

To conclude the section, let us introduce the possibility of counter-manipulation, i.e., let us expand the notion of GSgames by letting sincere players respond to hypothetic manipulations by strategic voters.

Example 7. We show that a 2-by-2 game with one manipulator and one counter-manipulator may not have a Nash equilibrium. Suppose that the voting rule is 2-approval and the profile is V = (adcb, bdca) with ties broken according to a > b > c > d. For voter 1 switching c and d is a manipulation in favor of a. To counter-manipulate, voter 2 can also switch c and d, making c win. But then voter 1 would be better off switching c and d back, after which the same move will be beneficial for voter 2.

5 Weak Dominance

In this section, we consider the complexity of checking whether a given GS-manipulation is always at least as good as the truthful vote. This problem is captured by the gametheoretic notion of weak dominance.

Definition 8. Given a GS-game G = (V,R, (Ai)i∈N(V,R)) and two strategies v∗ i , v∗∗ i ∈ Ai, we say that v∗ i weakly dominates v∗∗ i if for every profile V ′ ∈ GSP(G) either R(V ′-i , v∗ i ) = R(V ′-i , v∗∗ i ) or voter i prefers R(V ′-i , v∗ i ) to R(V ′-i , v∗∗ i ). We say that v∗ i is weakly dominant if v∗ i weakly dominates v∗∗ i for every v∗∗ i ∈ Ai.

In what follows, we will mostly be interested in determining whether a given GS-manipulation v∗ i weakly dominates the truthful vote vi. A related problem is whether v∗ i isweakly dominant. However, in the context of GS-games the former problem appears to be more relevant than the latter. Indeed, the main issue faced by a GS-manipulator is whether to manipulate or not, and if a certain vote can always ensure an outcome that is no worse than that of truthful voting, then this is a strong incentive to use it, even if another non-truthful vote may sometimes be better. Our approach is consistent with the one taken in the study of safe manipulation [Slinko and White, 2008; 2014], where different manipulations are not compared to each other either.

Preliminary Observations In the rest of the paper, we limit our attention to k-approval rules. We will now state some definitions and observations that apply to this class.

Note first that under k-approval any GS-manipulation of voter i is equivalent to a vote of the form vi[X; Y ], where X ⊆ topk(vi), Y ⊆ C \ topk(vi). Consider a GSmanipulation vi[X; Y ] of voter i in V under k-approval; we say that vi[X; Y ] is minimal if for every other GSmanipulation v′i of voter i it holds that v′i = vi[X′ ; Y ′ ], where |X′ | ≥ |X|. That is, a GS-manipulation is minimal if it performs as few swaps as possible.

Consider a profile V such that the k-approval winner in V is w, and sck(w, V ) = t. Recall that > is the tie-breaking order over candidates. Let

and set S(V, k) = S1 (V, k) ∪ S2 (V, k). We say that a candidate c is k-competitive in V if c ∈ S(V, k). Consider a GSmanipulator i who has a GS-manipulation in favor of some candidate p. As i prefers p to w, it cannot be the case that, by submitting a non-truthful vote, he both decreases the score of w and increases the score of p. Thus, his manipulation increases the score of p or decreases the score of w, but not both. It follows that under k-approval every GS-manipulation in V is in favor of some candidate p ∈ S(V, k); in particular, if V admits a GS-manipulator under k-approval, then S(V, k) is not empty.

There are two types of GS-manipulators: those who rank w in top k positions, and those who do not. The GSmanipulators of the first type can only manipulate in favor of candidates they already approve of, so in their manipulation they rank w in position k + 1 or lower; we will refer to such voters as demoters. The GS-manipulators of the second type manipulate by promoting some candidate they rank above w into top k positions; we refer to such voters as promoters. We say that a candidate c is k-plausible for i in V if there exists a promoter j ̸= i and a GS-manipulation v∗ j such that c is the k-approval winner in (V-j, v∗ j ); we denote the set of all candidates that are k-plausible for i in V by S+ i (V, k), and set S+(V, k) = ∪i∈NS+ i (V, k).

Plurality Consider a GS-manipulator i in a profile V under Plurality, and let v∗ i be his GS-manipulation. Note that i is necessarily a promoter. Let pi be i's favorite candidate in S(V, k) \ {top(vi)}. It is clear that v∗ i is equivalent to vi[top(vi); pi] and pi is the winner in (V-i, v∗ i ), i.e., all GS-manipulations of voter i in V are equivalent to each other. Hence, there is essentially a unique GSgame that corresponds to V , namely, the one where Ai = {vi, vi[top(vi); pi]} for each player i; we will denote this game by G∗1 (V ). We will now characterize GS-manipulations that are weakly dominant in this game (as each player i has two strategies, her GS-manipulation v∗ i is weakly dominant if and only if it weakly dominates vi).

Theorem 9. Let v∗ i be the GS-manipulation of voter i in G∗1 (V ), and let c = top(vi). Then v∗ i is weakly dominant in G∗1 (V ) if and only if c ̸∈ S+ i (V, 1).

Proof. Suppose that c ∈ S+ i , i.e., there exists a promoter j ̸= i with GS-manipulation v∗ j such that c wins in V 1 = (V-j , v∗ j ). Note that c = top1(v∗ j ). Consider the profile V 2 = (V 1-i , v∗ i ). In this profile both c and the initial winner w have the same score as in V , so c loses to w. As c = top(vi), this shows that v∗ i is not weakly dominant.

Conversely, suppose that c ̸∈ S+ i . Then for any profile V ′ = (v′1 , . . . , v′n ) ∈ GSP(G∗1 (V )) such that v′i = vi we have sc1(c, V ′ ) ≤ sc1(c, V ). On the other hand, since no GSmanipulator ranks w first, we have sc1(w, V ′ ) = sc1(w, V ). Thus, c is not the Plurality winner in V ′ . Let w′ be the Plurality winner in V ′ ; note that w′ ∈ {w}∪S. Let V ′′ = (V ′-i , v∗ i ). Suppose that v∗ i = v[c; p]. It is easy to see that this implies that the Plurality winner in V ′′ is either p or w′ . Since i weakly prefers p to every other candidate in {w} ∪ S, it follows that v∗ i is weakly dominant.

Theorem 9 illustrates that every GS-game for Plurality in the absence of dominant strategies is essentially a coordination game: the GS-manipulators have to coordinate to ensure that their efforts do not cancel out. We obtain the following:

Corollary 10. There is a polynomial-time algorithm for checking whether a given GS-manipulation v′i of voter i weakly dominates his truthful vote vi in G∗1 (V ).

2-Approval: An Algorithm We will now focus on the 2approval rule. Let w be the 2-approval winner in V , and recall that p∗ is the candidate in S that beats every other candidate in S in profile V under 2-approval. It can be shown that all demoters rank the same candidate p∗ first, and have the same set of GS-manipulations. Now, suppose that w ̸∈ top2(vi), i.e., i is a promoter. Then i can raise the scores of some candidates in C \top2(vi) by moving these candidates into top two positions; note that i can do that for two candidates simultaneously. Clearly, a promoter's vote is a GS-manipulation if and only if one of the promoted candidates is i's most preferred candidate in S \ top2(vi) (let us denote this candidate by p) and the other promoted candidate p′ is such that promoting p′ does not prevent p from becoming a winner. We emphasize that p is not necessarily i's most preferred 2-competitive candidate: it may be the case that i ranks another 2-competitive candidate in top two positions.

Given a profile V , let G∗2 (V ) be the GS-game where each player's set of actions consists of his truthful vote and all his minimal manipulations. The argument above shows that for demoters the minimality assumption imposes no additional constraints, whereas for promoters it excludes manipulations where two candidates are swapped into top two positions simultaneously.

We can now state the main result of this section, whose proof is omitted in the interest of space.

Theorem 11. There is a polynomial-time algorithm for checking whether a given GS-manipulation v′i of voter i weakly dominates his truthful vote vi in G∗2 (V ).

4-Approval: A Hardness Proof We were unable to determine the complexity of checking whether a given GS-manipulation weakly dominates truthtelling under 3approval. We conjecture that this problem is computationally hard. Indeed, this is the case for 4-approval: there is a way to select one manipulative action per player so that for the resulting game this problem is coNP-complete.

We reduce from the classic NP-complete problem EXACT COVER BY 3-SETS (X3C). An instance of this problem is given by a ground set Γ = {g1, . . . , g3ν} and a collection Σ = {σ1, . . . , σµ} of 3-element subsets of Γ. It is a "yes"- instance if there is a subcollection Σ′ ⊆ Σ with |Σ′ | = ν such that ∪σ∈Σ′σ = Γ, and a "no"-instance otherwise.

Theorem 12. The problem of deciding whether a given strategy v∗ i weakly dominates truthtelling in a GS-game (V, 4-App, (Ai)i∈N(V,4-App)) is coNP-complete.

Proof sketch. It is immediate that this problem is in coNP. To prove coNP-hardness, consider an instance I = (Γ, Σ) of X3C with |Γ| = 3ν, |Σ| = µ. We can assume without loss of generality that σ1 = {g1, g2, g3} and no other set in Σ contains g1; if this is not the case, we can modify I by adding three new elements and a single set containing them. We will now construct an instance of our problem. In what follows, when writing X ≻ Y in describing an order ≻, we mean that all elements of X are ranked above all elements of Y , but the order of elements within X and within Y can be arbitrary.

There is a set of candidates C ′ = {c1, . . . , c3ν} that correspond to elements of Γ, three special candidates w, p, and c, and a set of dummy candidates D = ⋃µi=0 Di, where |Di| = 4 for i = 0, . . . , µ. We define the order > by setting w > c > p > c1 > · · · > c3ν > D.

For each set σi ∈ Σ we construct a vote vi of the form

where candidates in σi are ordered according to >, and set

We also construct additional voters so that in the resulting profile V we have sc4(w, V ) = sc4(p, V ) = ν + 1, sc4(ci, V ) = ν + 1 for all i = 1, . . . , 3ν, sc4(c, V ) = 1, the 4-approval score of each candidate in D is at most 1, and the only GS-manipulators in V are voters 0, 1, . . . , µ.

Note that w is the 4-approval winner in V , and S = C ′ ∪ {p}. We now define a GS-game for this profile by constructing the players' sets of actions as follows. Let D0 = {d1, d2, d3, d4}. Then v∗ 0 = v0[{d1, d2}; {p, c}] is a GS-manipulation for voter 0, which makes p the winner with ν + 2 points. Similarly, for each i = 1, . . . , µ the vote v∗ i = vi[Di; σi ∪ {c}] is a GS-manipulation which makes i's top candidate in σi the winner with ν + 2 points (note that i orders σi in the same way > does, so tie-breaking favors i's most preferred candidate in σi). We set Ai = {vi, v∗ i } for i = 0, . . . , µ. This completes the description of our game. Clearly, we can construct the profile V and the players' sets of strategies in polynomial time given I. It can be shown that v∗ 0 weakly dominates v0 if and only if we started with a "no"-instance of X3C; we omit the proof.

6 Nash Equilibrium

In this section, we study existence and uniqueness of Nash equilibria in GS-games for k-approval with k = 1, 2, 3, 4. In what follows, when considering a GS-game, we assume that its set of GS-manipulators is not empty, since otherwise a Nash equilibrium exists trivially.

We will first show that for Plurality, a Nash equilibrium always exists.

Theorem 13. For any profile V the game G∗1 (V ) has a Nash equilibrium in pure strategies.

Proof. Consider the set S+(V, 1), and let p be the candidate with the highest score in this set (using the tie-breaking order eventually). Let i be some voter whose GS-manipulation is in favor of p, and let v∗ i = vi[top(vi); p]. Then (V-i, v∗ i ) is a Nash equilibrium with winner p.

However, many preference profiles admit multiple Nash equilibria under Plurality. For instance, if there are three voters i, j, ℓ such that vr[top(vr); c] ∈ Ar for each r ∈ {i, j, ℓ} and some candidate c, then there is a NE where these three voters manipulate and everyone else votes truthfully; if there are several candidates for whom such a triple of voters exists, any of them could win in a Nash equilibrium.

For 2-approval, we can prove existence of Nash equilibria as long as every manipulator has at least one minimal GSmanipulation in her action set.

Theorem 14. Any game G = (V, 2-App, (Ai)i∈N(V,2-App)), where for each i ∈ N(V, 2-App) the set Ai contains some minimal manipulation of voter i, has a Nash equilibrium.

Proof. We can assume that N(V, 2-App) ̸= ∅. Let w be the current winner of the election. Assume first that the set of promoters in G is not empty. Let p+ be the 2-plausible candidate that beats all other candidates in S+(V, 2). Let i be a promoter who manipulates in favor of p+, and let v∗ i be some minimal GS-manipulation of i. Then V ∗ = (V-i, v∗ i ) is a Nash equilibrium with winner p+. Indeed, by minimality of v∗ i we know that only the score of p+ has increased in V ∗ . Hence, to prevent p+ from winning in V ∗ , a manipulator j would have to lower p+'s score, and he could only do that if p+ ∈ top2(vj). If j is a promoter, then he prefers p+ to any candidate that he could make a winner in this way. On the other hand, if j is a demoter then p+ is his top candidate, hence he does not have incentives to change the outcome.

If all GS-manipulators are demoters, then a profile where any demoter, say j, submits a GS-manipulation and everyone else votes truthfully is a Nash equilibrium with winner top(vj). Indeed, a demoter can only manipulate in favor of her top candidate by decreasing the score of w. Hence all demoters manipulate in favor of the same candidate.

A similar result holds for 3-approval, though under stronger assumptions. Given a voter i and a set of candidates Z,we denote by boti(Z) the least preferred candidate of i in Z. A manipulative vote vi[X; Y ] is called greedy if it is minimal and for every other minimal strategy vi[X; Y ′ ] it holds that i prefers boti(Y ) to boti(Y ′ ). Clearly, there is a unique greedy manipulation for each manipulator i.

Theorem 15. The game G = (V, 3-App, (Ai)i∈N(V,3-App)) where for each i ∈ N(V, 3-App) the set Ai consists of i's truthful vote and her greedy GS-manipulation has a Nash equilibrium.

The restriction to greedy strategies in Theorem 15 is essential. Moreover, for 4-approval the existence of Nash equilibria is not guaranteed; we conjecture that this result extends to kapproval with k > 4.

Theorem 16. Under 3-approval, there exists a game G = (V, 3-App, (Ai)i∈N(V,3-App)), where for each player i ∈ N(V, 3-App) the set Ai consists of i's truthful vote and some minimal manipulations, s.t. G has no Nash equilibrium.

Theorem 16 holds even if we restrict the set of strategies of each player to her greedy manipulations:

Theorem 17. Under 4-approval, there exists a game G = (V, 4-App, (Ai)i∈N(V,4-App)), where for each player i ∈ N(V, 4-App) the set Ai consists of i's truthful vote and her greedy GS-manipulation, s.t. G has no Nash equilibrium.

7 Conclusions

In this paper we have studied the strategic interaction of manipulators in an electoral situation, providing a formal model in the form of a class of strategic-form games, which we called GS-games, and showing that these games may require extensive communication and a non-trivial computational effort to be played, which may serve as a barrier against manipulation. In particular, we have shown that for Plurality these games exhibit a fairly simple structure, which still allows for situations as complex as a coordination game. For Borda and k-approval, with k > 1, GS-games are quite complicated, and it may therefore be difficult for the players to coordinate their actions: indeed, for large enough k a Nash equilibrium may fail to exist, and even if it exists, it is not necessarily unique.

Many questions concerning GS-games remain open. The most immediate of them is to fully understand the role of minimality assumptions in our proofs. Further afield, it would be interesting to extend our study to other voting rules, and to identify reasonable restrictions on the manipulators' strategy spaces that lead to existence and uniqueness of Nash equilibria, and make it easy to compute manipulations that weakly dominate truthtelling.

Acknowledgements

Part of this work was done when Arkadii Slinko was visiting the Institute for Mathematical Sciences (Singapore) and the University of Padova (Italy). Francesca Rossi and Umberto Grandi were partially supported by the strategic project "KIDNEY - Incorporating patients' preferences in kidney transplant decision protocols" of the University of Padova.