The Complexity of Manipulative Attacks in Nearly Single-Peaked Electorates (Extended Abstract)

1 Introduction

Elections are a model of collective decision-making so central in human and multiagent-systems contexts-ranging from planning to collaborative filtering to reducing web spamthat it is natural to want to get a handle on the computational difficulty of finding whether manipulative actions can obtain a given outcome (see the surveys of Faliszewski et al. [2010; 2009b] and Brandt et al. [2013]). A recent line of work [Walsh, 2007; Faliszewski et al., 2011; Brandt et al., 2010a] started by Walsh [2007] has looked at the extent to which NP-hardness results for the complexity of manipulative actions may evaporate when one focuses on electorates that are single-peaked, a central social-science model of electoral behavior. That model basically views society as polarized along some (perhaps hidden) issue or axis.

However, real-world elections are unlikely to be perfectly single-peaked. Rather, they are merely very close to being single-peaked, a notion that was recently raised in a computational context by Conitzer [2009] and Escoffier et al. [2008]. There will almost always be a few mavericks, whose vote is based on some reason having nothing to do with the societal axis. For example, in recent US presidential primary and final elections, commentators discussed whether some voters might vote not based on the political positioning of the candidates but rather based on the candidates' religion or race. In

∗This paper is an extended abstract of the AI Journal publication [Faliszewski et al., 2014]. A preliminary version was presented at TARK-2011.

Lane A. Hemaspaandra

University of Rochester Rochester, NY, USA

this paper, we study whether the evaporation of complexity results that often holds for single-peaked electorates will also occur in nearly single-peaked electorates. We prove that often the answer is yes, and sometimes the answer is no. Below we outline the most important contributions of our work.

A collection of votes is said to be single-peaked if all the votes are consistent with some societal axis (we provide formal definition later). We consider four natural notions of nearness to single-peakedness for elections. The four notions are the following: (a) we allow some number of "maverick" voters, whose preferences need not respect the societal axis, (b) all voters must be consistent with the societal order when we disregard each voter's top preferred candidate (that is, each voter may have "swooned" regarding his or her top choice), (c) every vote is within a small number of adjacentcandidate swaps of respecting the societal order, and (d) all the votes are consistent with some axis, but that axis may be one that is not the societal axis but rather is within a small number of adjacent-candidates swaps of the original axis. For each of these notions we show how, given the society's axis, to compute in polynomial time how much the voters diverge from single-peakedness according to that notion. 1

We establish the complexity of coalitional weighted manipulation under 3-candidate scoring protocols for nearly single-peaked elections. In Table 1, we show that even a very slight deviation from single-peakedness, under any of our four distance models, can raise the manipulation complexity from P, which is what holds in the (perfectly) singlepeaked case, to being as hard as in the unrestricted case. Moving beyond three candidates, we extend our study of manipulation to m-candidate veto, for each m (see Table 2; there is a relationship between m and the amount of divergence from single-peakedness that can be handled in polynomial time).

We show, in all but one of the cases that we study, that the complexity of control problems for plurality, k-approval, and approval elections that are nearly single-peaked is the same as the control complexity for elections where the voters are (perfectly) single-peaked. For the only case (control by deleting voters under t-approval elections and swoon-SP societies; see Section 3 for the definitions) in which we do not reach the same result as for the case of single-peaked elections, we construct a good polynomial-time approximation algorithm.

1 For notion (b), the society either does or does not satisfy the condition, so we provide a polynomial-time decision algorithm.

2 Preliminaries

Elections and Election Systems. An election E = (C, V ) consists of a finite candidate set C and a finite collection V of votes over the candidates. V is a list of entries, one per voter, with each entry containing a linear (i.e., total) ordering of the candidates. If an election is weighted then each voter, additionally, has an integer weight. A voter with weight w is treated as w unweighted voters with the same preferences.

An election systemR is a function that takes as its input an election instance E = (C, V ) and outputs a set W ⊆ C. Member(s) of W are described as winner(s) of the given election. Plurality is arguably the most important election system. In plurality elections, whichever candidate gets the most top-of-the-preference-order votes wins. Each vector (α1, . . . , αm), αi ∈ N, α1 ≥ · · · ≥ αm ≥ 0, defines an m-candidate scoring protocol election rule, in which each voter's ith favorite candidate gets αi points, and whichever candidate gets the most points wins. m-candidate Borda is defined by the vector (m - 1,m - 2, . . . , 0). For each m and t, 0 < t < m, m-candidate t-approval is defined by the vector of t ones followed by m- t zeroes, (m-candidate) tveto is a synonym for (m-candidate) (m- t)-approval, and (m-candidate) veto is a synonym for (m-candidate) 1-veto. We will also, as is common, often use t-veto (respectively, tapproval) to refer to the system with no bound on the number of candidates that on each input having m candidates applies m-candidate t-veto (respectively, m-candidate t-approval). In all the systems just mentioned, if candidates tie for the highest number of points, those that tie for highest are all considered winners.

Under approval voting (a system which should not be confused with t-approval) we assume that the votes are not linear orders but are ‖C‖-long 0-1 vectors denoting disapproval/approval of each candidate. The candidates approved by the largest number of the voters are the winners.

Attacks. Let us now describe the types of attacks that we study. Due to limited space, instead of formal definitions we provide sketches and point the reader to the full version of the paper for details [Faliszewski et al., 2014].

The constructive coalitional manipulation problem for weighted elections (CCWM) models situations where a group of voters (in a weighted election) seeks to make a particular candidate a winner, and wants to know whether there exist votes that they can cast that will make that happen. That is, given a voting rule R, in R-CCWM we are given a set of candidates C, a collection S of weighted nonmanipulative voters (with weights and preference orders), a collection T of manipulative voters (with weights but without preference orders), and a preferred candidate p ∈ C. We ask if it is possible to set the preferences of the voters in T so that p is an R-winner of election (C, S ∪ T ).

Control loosely models such real-world activities as getout-the-vote drives, targeted advertising, and voter suppression. In each of the four types of control that we discuss, the input contains an election E = (C, V ), the candidate p ∈ C that one wants to be a winner, and a parameter K limiting how many actors one can influence in the designated way. Our four types of control are adding voters (CCAV), deleting voters (CCDV), adding candidates (CCAC), and deleting candidates (CCDC). 2 In the "adding" variants, CCAC and CCAV, the input also contains, respectively, either the set of candidates that we can add (the voters have preferences over both the original candidates and those that can be added) or the set of voters that we can add. Each of these four problems is defined as the collection of inputs on which using at most K actions of the designated type (e.g., adding at most K voters) can suffice to make p a winner.

Each of our algorithms for manipulation and control not only gives a yes/no answer for the decision variant of the problem, but also can be made to produce a successful manipulative action if the answer is yes; see the work of Hemaspaandra et al. [2013] for why this distinction is important.

3 Nearly Single-Peaked Societies

Imagine that on some issue, for example what the tax rate should be for the richest Americans, each person has a utility curve that on a (perhaps empty) initial part is nondecreasing and then on the (perhaps empty) rest is nonincreasing. Suppose the candidates are spread along the tax-rate axis as to their positions, with no two on top of each other. The sets of preferences that can be supported among them by curves of the mentioned sort on which there are no ties among candidates in utility are precisely the single-peaked vote ensembles. Note that different voters can have different peaks/plateaus and different curves, e.g., if both Alice and Bob think 40 percent is the ideal top tax rate, it is completely legal for Alice to prefer 30 percent to 50 percent and Bob to prefer 50 percent to 30 percent.

Formally, single-peakedness of a collection of votes with respect to a given societal order (which following Walsh [2007] will be our standard model), or without a societal order being given, is defined as follows.

Definition 3.1 ([Black, 1948; 1958], see also the work of Arrow [1951 revised editon 1963]). A collection V of votes (cast as linear orders) is said to be single-peaked with respect to L (see Faliszewski et al. [2011]), where L is a linear order over the candidate set, if for each triple of candidates, c1, c2, c3, it holds that if c1 Lc2 Lc3 ∨ c3 Lc2 Lc1, then (∀v ∈ V )[c1 >v c2 =⇒ c2 >v c3], where a >v b means that voter v prefers a to b. A collection V of votes (cast as linear orders) is said to be single-peaked exactly if there is a linear order L, over the candidate set, such that V is single-peaked with respect to L.

We omit the definition of single-peakedness for approval voting, which is due to Faliszewski et al. [2011], and point the reader directly to that paper or to the full version of the present paper.

We focus on elections whose voters are "nearly" singlepeaked, under the following notions of nearness.

2 These four-letter abbreviations that start with "CC" are the established shorthand for these problems in the literature. The "CC" is short for "constructive control by," and it means that these control problems are about trying to make a given candidate win an election.

Definition 3.2. Let V be a collection of votes (cast as linear orders), let L be a linear order over the candidate set (the societal axis), and let k be a nonnegative integer.

1. We say that V is a k-maverick-SP society with respect to the axis L if there is a subcollection, W, W ⊆ V , of at most k votes, such that V -W is single-peaked with respect to L.
2. We say that V is a swoon-SP society with respect to the axis L if for each vote v in V it holds that v with the top candidate removed is single-peaked with respect to L (with the same candidate removed).
3. We say that V is a Dodgsonk-SP society with respect to the axis L if for each vote v in V there exists a vote v′ that is single-peaked with respect to L and that can be obtained from v by at most k (sequential) swaps of adjacent candidates.
4. We say that V is a PerceptionFlipk-SP society with respect to the axis L if for each vote v in V there exists an axis Lv such that (a) {v} is single-peaked with respect to Lv, and (b) Lv can be obtained from L by at most k (sequential) swaps of adjacent candidates.

In all our manipulative action problems about singlepeaked and nearly single-peaked societies, we will follow the model of Walsh [2007], which is that the societal order, L, is part of the input. Because of this, we henceforward when speaking of single-peakedness or nearness to singlepeakedness, for some manipulative action, will often leave out the phrase "with respect to a given axis L."

We refer the reader to earlier papers, e.g., those of Walsh [2007], Brandt et al. [2010b], and Faliszewski et al. [2011], for a discussion of why Walsh's model is reasonable. One important technical benefit of using Walsh's model is that for nearly single-peaked societies the difference between knowing the axis and not knowing it may have a tremendous impact on the complexity of electionrelated problems. For example, as Theorem 3.3 below we will soon show that finding the distance from a vote collection to a given societal ordering can be done in polynomial time. In contrast with this, Erdélyi et al. [2012] and Bredereck et al. [2013]-motivated by an earlier version of the present paper-have shown that, for example, deciding whether a given collection of voters forms a k-maverick-SP society, where k itself is not globally fixed but rather is part of the input, is NP-complete. The same holds for the case of Dodgsonk-SP societies, by the work of Erdélyi et al. [2012], who there use the term "local swaps" to refer to this one of our distance models. For context and comparison, we mention that for perfectly single-peaked societies, both in the case of linear-order voters and in the case of approval votes, in polynomial time one can test consistency with an axis, in polynomial time one can find whether there exists an axis with which the society is consistent, and in polynomial time one can even produce an axis with which the society is consistent when such an axis exists [Bartholdi and Trick, 1986; Escoffier et al., 2008; Doignon and Falmagne, 1994; Booth, 1978; Fulkerson and Gross, 1965]; see the discussion at the end of Section 2.2 of the work of Faliszewski et al. [2011].

We show that given an axis it is easy to find "how nearly single-peaked" a society is with respect to this axis.

Theorem 3.3. There are polynomial-time algorithms that given a collection V of voters and a linear order L compute the smallest k such that V is a: (1) k-maverick-SP society with respect to L, (2) Dodgsonk-SP society with respect to L, and (3) PerceptionFlipk-SP society with respect to L. There is also a polynomial-time algorithm that given the same input decides if V is a swoon-SP society.

We assume that our requirements regarding nearness to single-peakedness are for all the voters that appear in our problems (both before and after each manipulative action).

4 Results

We summarize our results regarding manipulation in Tables 1 and 2. The results for control are in Table 3. The results for the general case and for the single-peaked cases listed in these tables are due to other papers [Bartholdi et al., 1992; Elkind et al., 2011; Lin, 2012; Hemaspaandra et al., 2007; Faliszewski et al., 2011]; the journal version of this paper contains detailed references.

Regarding manipulation, our results are varied. We first focus on the complexity of manipulation, under our four notions of nearness to single-peakedness, for 3-candidate weighted elections (Table 1; briefly put, being even slightly away from perfect single-peakedness gives the same hardness results as in the unrestricted case). Then we provide some additional results for larger veto elections (Table 2; there is a simple relation between the number of candidates and the divergence from single-peakedness for which we can still provide polynomial-time algorithms).

For the case of control, we provide results for plurality, tapproval, and approval. We chose these rules because they show quite interesting, contrasting behavior with respect to the complexity of control. Under unrestricted preferences, for plurality it holds that candidate control problems are NPcomplete but voter control problems are easy. For approval, we have the opposite: candidate control is easy and voter control is hard. For t-approval (for t ≥ 4), all candidate and voter control problems are hard. In contrast, for single-peaked societies all these control problems for these voting rules are easy. We show that these easiness results typically translate to the case of nearly single-peaked elections.

Since approval voting does not use linear orders, distance models inherently based on linear orders have "N/A" in their approval-voting cells of the table.

5 RelatedWork

For references on history, context, discussions, and results regarding the computational complexity of control and manipulation, we point the reader to the surveys of Faliszewski et al. [2009b; 2010]. For example, it is known that there exist election systems that are resistant to many control attacks [Erdélyi et al., 2009; 2015; Faliszewski et al., 2009a; Hemaspaandra et al., 2009].

The four papers most related to the present one are the following. Walsh [2007] insightfully raised the idea that general complexity results may change in single-peaked societies. Faliszewski et al. [2011] and Brandt et al. [2010a] then broadly explored the effect of single-peakedness on manipulative actions. These three papers are all in the model of (perfect) single-peakedness. Conitzer [2009], in the context of preference elicitation, raised and studied the issue of nearly single-peaked societies. Escoffier et al. [2008] also discussed nearness to single-peakedness, and Faliszewski et al. [2011] and Brandt et al. [2010a] raise as open issues whether shield-evaporation (complexity) results for single-peakedness will withstand near-single-peakedness, i.e., whether, in cases where a general-case NP-hardness result drops to P for singlepeaked electorates, the complexity will stay in P even for nearly single-peaked electorates. The present paper's focus is bringing such a "nearly single-peaked" lens to the study of manipulative actions. Subsequent work by Cornaz et al. [2012] discusses a similar notion of nearness to singlepeakedness in the context of winner determination under Chamberlin and Courant's proportional representation voting rule, and the paper of Elkind et al. [2012], among other issues, studies algorithms for measuring society's nearness to single-peakedness through removing clones, i.e., candidates that all voters rank in consecutive blocks.

6 Conclusions

Motivated by the fact that real-world electorates are unlikely to be flawlessly single-peaked, we have studied the complexity of manipulative actions on nearly single-peaked electorates. Often, a modest amount of non-single-peaked behavior is not enough to obliterate an existing polynomialtime claim. We find this the most important theme of this paper-its "take-home message." So if one feels that previous polynomial-time manipulative-action algorithms for singlepeaked electorates are suspect since real-world electorates tend not to be truly single-peaked but rather nearly singlepeaked, our results of this sort should reassure one on this point-although they are but a first step. Yet we also found that sometimes allowing even one deviate voter is enough to raise the complexity from P to NP-hardness.

Acknowledgments. We are grateful to anonymous referees, whose comments improved our paper. Piotr Faliszewski was supported in part by AGH University of Technology grant 11.11.230.124. Edith Hemaspaandra was supported in part by grants NSF-IIS-0713061 and NSF-CCF-1101452, and a Friedrich Wilhelm Bessel Research Award. Lane A. Hemaspaandra was supported in part by grants NSF-CCF0915792, NSF-CCF-1101479, and ARC-DP110101792, and a Friedrich Wilhelm Bessel Research Award.