You are an expert at summarizing long articles. Proceed to summarize the following text: 
elections are a general and widely used framework for preference aggregation in human and artificial intelligence applications . an important negative result from social choice theory , the gibbard - satterthwaite theorem  @xcite , states that every reasonable election system is manipulable . however , even though every election system is manipulable , it may be computationally infeasible to determine how to manipulate the outcome . bartholdi , tovey , and trick   introduced the computational study of the manipulation problem and this began an exciting line of research that explores the computational complexity of different manipulative attacks on elections ( see , e.g. ,  @xcite ) . the notion of single - peaked preferences introduced by black   is the most important restriction on preferences from political science and economics and is naturally an important case to consider computationally . single - peakedness models the preferences of a collection of voters with respect to a given axis ( a total ordering of the candidates ) . each voter in a single - peaked election has a single most - preferred candidate ( peak ) on the axis and the farther candidates are to the left / right from her peak the less preferred they are . single - plateauedness extends this to model when each voter has multiple most - preferred candidates that appear sequentially on the axis , but are otherwise single - peaked  @xcite . this standard model of single - peaked preferences has many desirable social - choice properties . when the voters in an election are single - peaked , the majority relation is transitive  @xcite and there exist voting rules that are strategy - proof  @xcite ( i.e. , a voter can not misrepresent her preferences to achieve a personally better outcome ) . single - peakedness for total orders can also have an effect on the complexity of many different election attack problems when compared to the general case . the complexity of manipulative attacks often decreases when the voters in an election are single - peaked  @xcite , and the winner problems for kemeny , dodgson , and young elections are in p  when they are @xmath0-complete in general  @xcite . most of the abovementioned research on the computational complexity of manipulation of elections , both for the general case and for single - peaked electorates , has been limited to the assumption that voters have tie - free votes . in many real - world scenarios voters have votes with ties , and this is seen in the online repository preflib  @xcite that contains several different preference datasets that contain ties . there are also election systems defined for votes with ties , e.g. , the kemeny rule and the schulze rule  @xcite . recent work considers the complexity of manipulation for top - order votes ( votes where all of the ties are between candidates ranked last )  @xcite . fitzsimmons and hemaspaandra   considered the complexity of manipulation , control , and bribery for more general votes with ties , and also the case of manipulation for a nonstandard model of single - peakedness for top - order votes . menon and larson   later examined the complexity of manipulation and bribery for an equivalent ( for top orders ) model of single - peakedness . fitzsimmons and hemaspaandra   use the model of possibly single - peaked preferences from lackner   where a preference profile of votes with ties is said to be single - peaked with respect to an axis if the votes can be extended to tie - free votes that are single - peaked with respect to the same axis . menon and larson   use a similar model for top orders that they state is essentially the model of single - peaked preferences with outside options  @xcite . both fitzsimmons and hemaspaandra   and menon and larson find that these notions of single - peakedness exhibit anomalous computational behavior where the complexity of manipulation can increase when compared with the case of single - peaked total orders . we are the first to study the computational complexity of manipulation for the standard model of single - peaked preferences for votes with ties , and for single - plateaued preferences for votes with ties . in contrast to the recent related work using other models of single - peakedness with ties , we find that the complexity of weighted manipulation for @xmath1-candidate scoring rules and for @xmath1-candidate copeland@xmath2 elections for all @xmath3 does not increase when compared to the cases of single - peaked total orders , and that the complexity of weighted manipulation does not increase with respect to the general case of elimination veto elections . we also compare the social choice properties of these different models , and state a surprising result on the relation between the societal axis and the complexity of manipulation for single - peaked preferences . an _ election _ consists of a finite set of candidates @xmath4 and a finite collection of voters @xmath5 . we will sometimes refer to this collection of voters as a _ preference profile_. an _ election system _ @xmath6  is a mapping from an election to a set of winners , which can be any subset of the candidate set ( the nonunique winner model , our standard model ) , or at most a single candidate ( the unique winner model ) . each voter in an election has a corresponding vote ( or _ preference order _ ) over the set of candidates . this is often assumed to be a _ total order _ , i.e. , a strict ordering of the candidates from most to least preferred . formally , a total order is a complete , reflexive , transitive , and antisymmetric binary relation . we use `` @xmath7 '' to denote strict preference between two candidates .    similarly , a _ weak order _ is a total order without antisymmetry , so each voter can rank candidates as tied ( which we will sometimes refer to as indifference ) as long as their ties are transitive . we use `` @xmath8 '' to denote a tie between two candidates . a _ bottom order _ is a weak order where all ties are between top - ranked candidates and a _ top order _ is a weak order where all ties are between bottom - ranked candidates . notice that a total order is a weak order , a top order , and a bottom order , that a top order is a weak order , and that a bottom order is a weak order . throughout this paper we will sometimes refer to weak orders as votes with ties . for some of our results we consider weighted elections , where each voter has an associated positive integral weight and a voter with weight @xmath9 counts as @xmath9 unweighted voters all voting the same . our election systems include scoring rules , elimination veto , and copeland@xmath2 . we define each below and the extensions we use to properly consider votes with ties . given an election with @xmath1 candidates , a scoring rule assigns scores to the candidates using its corresponding @xmath1-candidate scoring vector of the form @xmath10 where @xmath11 and each @xmath12 . so , when the preferences of a voter are a total order , the candidate ranked in position @xmath13 receives a score of @xmath14 from that voter . below we present examples of scoring rules and their corresponding @xmath1-candidate scoring vector . * plurality : * with scoring vector @xmath15 .    * veto : * with scoring vector @xmath16 . * borda : * with scoring vector @xmath17 .    * triviality : * with scoring vector @xmath18 .    to use a scoring rule to determine the outcome of an election containing votes with ties we must extend the above definition of scoring rules . we use the definitions of scoring - rule extensions for weak orders from our previous work  @xcite , which generalize the extensions introduced for top orders from baumeister et al .   and from narodytska and walsh   which in turn generalizes the extensions used by emerson   for borda . given a weak - order vote , we can write it as @xmath19 , where each @xmath20 is a set of tied candidates , ( so in the case of a total order vote each @xmath20 is a singleton ) . for each @xmath20 , let @xmath21 be the number of candidates strictly preferred to the candidates in @xmath20 . we now state the definitions of each of the four extensions . in example [ ex : scoring - rule - ext ] we present an example of how a given weak - order vote is scored using borda and each of the scoring - rule extensions .    * min : * each candidate in @xmath20 receives a score of @xmath22 .    * max : * each candidate in @xmath20 receives a score of @xmath23 . * round down : * each candidate in @xmath20 receives a score of @xmath24 . * average : * each candidate in @xmath20 receives a score of @xmath25    for top orders the scoring - rule extensions min , round down , and average are the same as round up , round down , and average used in the work by menon and larson  . [ ex : scoring - rule - ext ] given the candidate set @xmath26 and the weak order vote @xmath27 we show the scores assigned to each candidate using borda and each of our extensions . we can write the vote as @xmath28 , so @xmath29 , @xmath30 , and @xmath31 , and @xmath32 , @xmath33 , and @xmath34 . recall that for total orders , the scoring vector for 5-candidate borda is @xmath35 . * borda using min : * @xmath36 , @xmath37 , and @xmath38 .    * borda using max : * @xmath39 , @xmath40 , and @xmath38 .    * borda using round down : * @xmath41 , @xmath37 , and @xmath38 .    * borda using average : * @xmath42 , @xmath43 , and @xmath38 .    for elimination veto for total orders , the veto scoring rule is used , the candidate with the lowest score is eliminated , and the rule is repeated on the remaining votes restricted to the remaining candidates until there is one candidate left  @xcite . we break ties lexicographically , and for comparison with related work our results for elimination veto use the unique winner model , and for votes with ties we use the min extension . pairwise election systems are one of the most natural cases for considering votes with ties . copeland@xmath2 is an important and well - known election system that is defined using pairwise comparisons between candidates . in a copeland@xmath2 election each candidate receives one point for each pairwise majority election with each other candidate she wins and @xmath44 points for each tie ( where @xmath45 and @xmath46 ) . for votes with ties we follow the obvious extension also used by baumeister et al .   and narodytska and walsh  . for copeland@xmath2 elections it will sometimes be easier to refer to the _ induced majority graph _ of an election . given an election @xmath47 its induced majority graph is constructed as follows . each vertex in the induced majority graph corresponds to a candidate in @xmath4 , and for all candidates @xmath48 if @xmath49 by majority then there is an edge from @xmath50 to @xmath51 in the induced majority graph . we also will refer to the _ weighted majority graph _ of an election , where each edge from @xmath50 to @xmath51 in the induced majority graph is labeled with the difference between the number of voters that state @xmath49 and the number of voters that state @xmath52 . the computational study of the manipulation of elections was introduced by bartholdi , tovey , and trick  , and conitzer , sandholm , and lang   extended this to the case for weighted voters and a coalition of manipulators . we define the constructive weighted coalitional manipulation ( cwcm ) problem below . * name : * @xmath53-cwcm    * given : * a set of candidates @xmath4 , a collection of nonmanipulative voters @xmath54 , a collection of manipulative voters @xmath55 , and a preferred candidate @xmath56 . * question : * does there exist a way to set the votes of @xmath55 such that @xmath57 is a winner of @xmath58 under election system @xmath53 ?    for the case of cwcm for each of our models of single - peaked preferences we follow the model introduced by walsh   where the societal axis is given as part of the input to the problem and the manipulators must state votes that are single - peaked with respect to this axis ( for the corresponding model of single - peakedness ) . ( see section  [ sec : variants ] for all of the definitions of single - peaked preferences that we use . )      for our np - completeness results we will use the following well - known np - complete problem . * name : * partition    * given : * given a collection of @xmath59 positive integers @xmath60 such that @xmath61 .    * question : * does there exist a partition of @xmath60 into two subcollections @xmath62 and @xmath63 such that @xmath64 ? we consider four important models of single - peaked preferences for votes with ties . for the following definitions , for a given axis @xmath65 ( a total ordering of the candidates ) and a given preference order @xmath66 , we say that @xmath66 is strictly increasing ( decreasing ) along a segment of @xmath65 if each candidate is preferred to the candidate on its left ( right ) with respect to @xmath65 . in figure [ fig : ex - peak ] we present an example of each of the four models of single - peaked preferences , and in figure  [ fig : relation ] we show how the four models relate to each other . we now give the definition of the standard model of single - peakedness from black  . [ def : standard ] given a preference profile @xmath5 of weak orders over a set of candidates @xmath4 , @xmath5 is single - peaked with respect to a total ordering of the candidates @xmath65 ( an axis ) if for each voter @xmath67 , @xmath65 can be split into three segments @xmath68 , @xmath69 , and @xmath70 ( @xmath68 and @xmath70 can each be empty ) such that @xmath69 contains only the most preferred candidate of @xmath66 , @xmath66 is strictly increasing along @xmath68 and @xmath66 is strictly decreasing along @xmath70 . observe that for a preference profile of votes with ties to be single - peaked with respect to an axis , each voter can have a tie between at most two candidates at each position in her preference order since the candidates must each appear on separate sides of her peak . otherwise the preference order would not be _ strictly _ increasing / decreasing along the given axis . the model of single - plateaued preferences extends single - peakedness by allowing voters to have multiple most preferred candidates ( an indifference plateau )  @xcite . this is defined by extending definition  [ def : standard ] so that @xmath69 can contain multiple candidates . lackner   recently introduced another extension to single - peaked preferences , which we refer to as `` possibly single - peaked preferences '' throughout this paper . a preference profile is possibly single - peaked with respect to a given axis if there exists an extension of each preference order to a total order such that the new preference profile of total orders is single - peaked . this can be stated without referring to extensions , for votes with ties , in the following way . given a preference profile @xmath5 of weak orders over a set of candidates @xmath4 , @xmath5 is possibly single - peaked with respect to a total ordering of the candidates @xmath65 ( an axis ) if for each voter @xmath67 , @xmath65 can be split into three segments @xmath68 , @xmath69 , and @xmath70 ( @xmath68 and @xmath70 can each be empty ) such that @xmath69 contains the most preferred candidates of @xmath66 , @xmath66 is weakly increasing along @xmath68 and @xmath66 is weakly decreasing along @xmath70 . notice that the above definition extends single - plateauedness to allow for multiple indifference plateaus on either side of the peak . so for votes with ties , possibly single - peaked preferences model when voters have weakly increasing and then weakly decreasing or only weakly increasing / decreasing preferences along an axis . another generalization of single - peaked preferences for votes with ties was introduced by cantala  : the model of single - peaked preferences with outside options . when preferences satisfy this restriction with respect to a given axis , each voter has a segment of the axis where they have single - peaked preferences and candidates appearing outside of this segment on the axis are strictly less preferred and the voter is tied between them . similar to how single - plateaued preferences extend the standard single - peaked model to allow voters to state multiple most preferred candidates , single - peaked preferences with outside options extends the standard model to allow voters to state multiple least preferred candidates .    given a preference profile @xmath5 of weak orders over a set of candidates @xmath4 , @xmath5 is single - peaked with outside options with respect to a total ordering of the candidates @xmath65 ( an axis ) if for each voter @xmath67 , @xmath65 can be split into five segments @xmath71 , @xmath68 , @xmath69 , @xmath70 , and @xmath72 ( @xmath71 , @xmath68 , @xmath70 , and @xmath72 can each be empty ) such that @xmath69 contains only the most preferred candidate of @xmath66 , @xmath66 is strictly increasing along @xmath68 and @xmath66 is strictly decreasing along @xmath70 , for all candidates @xmath73 and @xmath74 , @xmath66 states @xmath49 , and for all candidates @xmath75 , @xmath66 states @xmath76 . menon and larson   state that the model of single - peakedness for top orders that they use is similar to single - peaked preferences with outside options . it is clear from their paper that for top orders these models are the same . so for the remainder of the paper we will refer to the model used by menon and larson   as `` single - peaked preferences with outside options for top orders . '' , the solid line is the single - peaked order @xmath77 , the dashed line is the single - plateaued order @xmath78 , the dashed - dotted line is the single - peaked with outside options order @xmath79 , and the dotted line is the possibly single - peaked order @xmath80 . see figure  [ fig : relation ] for the relationships between the four models . ] we now state some general observations on single - peaked preferences with ties , including how the models relate to each other , as well as their social - choice properties . it is easy to see that for total - order preferences each of the four models of single - peakedness with ties that we consider are equivalent . in figure [ fig : relation ] we show how each model relates for weak orders , top orders , and bottom orders .    given a preference profile of votes it is natural to ask how to determine if an axis exists such that the profile satisfies one of the above restrictions . this is referred to as the consistency problem for a restriction . bartholdi and trick   showed that single - peaked consistency for total orders can be determined in polynomial time ( i.e. , is in p ) , and fitzsimmons   extended this result to show that single - peaked , single - plateaued , and possibly single - peaked consistency for weak orders is in p. this leaves the consistency problem for single - peaked preferences with outside options , which we will now show to be in p.    it is easy to see that given a preference profile of top orders , it is single - peaked with outside options if and only if it is possibly single - peaked . so it is immediate from the result by lackner   that shows that possibly single - peaked consistency for top orders is in p , that the consistency problem for single - peaked preferences with outside options for top orders is in p. for weak orders the construction used to show that single - peaked consistency for weak orders is in p   by fitzsimmons   can be adapted to hold for the case of single - peaked preferences with outside options for weak orders , so this consistency problem is also in p.    given a preference profile @xmath5 of weak orders it can be determined in polynomial time if there exists an axis @xmath65 such that @xmath5 is single - peaked with outside options with respect to @xmath65 . one of the most well - known and desirable properties of an election with single - peaked preferences is that there exists a transitive majority relation  @xcite . a majority relation is transitive if for all distinct candidates @xmath81 if @xmath49 and @xmath82 by majority then @xmath83 by majority . when the majority relation is transitive then candidates that beat - or - tie every other candidate by majority exist and they are denoted the weak condorcet winners . this also holds when the voters have single - plateaued preferences  @xcite . it is not the case that the majority relation is transitive when preferences in an election are single - peaked with outside options or are possibly single - peaked . fitzsimmons   points out that for possibly single - peakedness this was implicitly shown in an entry of table  9.1 in fishburn  , where a preference profile of top orders that violates single - peaked preferences was described that does not have a transitive majority relation , and this profile is possibly single - peaked ( and single - peaked with outside options ) . cantala also provides an example of a profile that is single - peaked with outside options that does not have a weak condorcet winner , and so does not have a transitive majority relation  @xcite . for total - order preferences , weighted manipulation for any fixed number of candidates is known to be np  for every scoring rule that is not isomorphic to plurality or triviality  @xcite . for single - peaked total orders , faliszewski et al .   completely characterized the complexity of weighted manipulation for 3-candidate scoring rules and this result was generalized by brandt et al .   for any fixed number of candidates . these results both showed that the complexity of weighted manipulation for scoring rules often decreases when voters have single - peaked total orders .    for top - order preferences , dichotomy theorems for 3-candidate weighted manipulation for scoring rules using round down , min , and average were shown by menon and larson for the general case  @xcite and for the case of single - peaked preferences with outside options for top orders  @xcite . menon and larson   found that , counterintuitively , the complexity of weighted manipulation for single - peaked preferences with outside options often increases when moving from total orders to top orders . we also mention that for the scoring - rule extension max , we earlier found that the complexity of 3-candidate weighted manipulation for borda increases for possibly single - peaked preferences when moving from total orders to top orders  @xcite . we show that for the standard model of single - peakedness and for single - plateauedness that the complexity of weighted manipulation for @xmath1-candidate scoring rules using max , min , round down , and average does not increase when moving from total orders to top orders , bottom orders , or weak orders . the following results are close analogs to the case for single - peaked total orders due to brandt et al .  . [ lem : sp - first ] if @xmath57 can be made a winner by a manipulation of top - order , bottom - order , or weak - order votes that are single - peaked , single - plateaued , possibly single - peaked , or single - peaked with outside options for a scoring rule using max , min , round down , or average , then @xmath57 can be made a winner by a manipulation ( of the same type ) in which all manipulators rank @xmath57 uniquely first . suppose that a manipulator has a vote of the form @xmath84 where @xmath85 is a weak order over @xmath62 ( where @xmath62 can be empty ) , @xmath86 , each of @xmath87 are nonempty groups of tied candidates , and @xmath88 . we have the following two cases . case 1 : : :    if all of the candidates in @xmath89 appear on the same side of    the candidates in @xmath62 with respect to the axis ( or    @xmath62 is empty ) , then we can change the vote of the    manipulator to    @xmath90    where @xmath91 and @xmath92    are total orders such that the vote satisfies the given notion of    single - peakedness with ties with respect to the axis . case 2 : : :    otherwise , we let @xmath93 be the candidates to the left of    @xmath62 and @xmath94 be the candidates to the right    of @xmath62 with respect to the axis . without loss of    generality let @xmath95 . we can then change the vote of    the manipulator to    @xmath96 . notice that in all of the above cases , for all candidates @xmath97 that @xmath98 does not decrease , regardless of which scoring - rule extension is used . so if @xmath57 is a winner with the initial vote , @xmath57 is still a winner in the vote that ranks @xmath57 uniquely first . [ thm : noninc ] let @xmath99 be a scoring vector . if @xmath44-cwcm is in p for single - peaked total orders , then @xmath44-cwcm is in p for single - peaked and single - plateaued top orders , bottom orders , and weak orders for all our scoring rule extensions . if the societal axis has @xmath57 in the leftmost or rightmost position , then , by lemma  [ lem : sp - first ] , we can assume that all manipulators rank @xmath57 uniquely first . there is exactly one such single - peaked or single - plateaued vote with ties , namely to rank @xmath57 first and strictly rank the remaining candidates according to their position on the axis . so , let the societal axis be @xmath100 . we first consider the p  cases for single - peaked total orders described in lemma  6.6 of brandt et al . where for all @xmath101 such that @xmath102 it holds that @xmath103 . the crucial observation in the proof of this lemma is that for every set of single - peaked total order votes @xmath54 , we are in one of the following two cases :    1 .   for all @xmath13 , @xmath104 , @xmath105 . 2 .   for all @xmath13 , @xmath106 , @xmath107 .    we will show that this is also the case for single - peaked and single - plateaued orders with ties . this then implies that the optimal vote for all manipulators is @xmath108 ( in case  1 ) or @xmath109 ( in case  2 ) .    for the sake of contradiction let @xmath54 be a collection of nonmanipulators and @xmath110 and @xmath111 be integers such that @xmath112 and @xmath113 such that @xmath114 and @xmath115 . we now create an @xmath116 such that @xmath117 and @xmath118 and the argument in the proof of lemma  6.6 in brandt et al .   still holds .    * first , remove from @xmath54 all voters that have @xmath57 tied for first . notice that if we remove all votes with @xmath57 tied for first from @xmath54 then @xmath119 does not increase and neither @xmath120 nor @xmath121 decreases . so we can assume that @xmath57 is never tied for first in a vote ( although this does not mean that other candidates can not be tied for first in a vote when we are in the single - plateaued case ) . * we know that @xmath57 is not tied for first ( part of an indifference plateau ) , so @xmath57 is tied with at most one other candidate in each vote . so in every vote break the tie against @xmath57 . notice that this can lower only the score of @xmath57 regardless of whether we are using the min , max , round down , or average scoring - rule extension . let @xmath122 be the total weight of the voters in @xmath116 that rank some candidate in @xmath123 first and @xmath57 in the position of @xmath14 ( in every extension other than round down this means that @xmath57 is ranked @xmath13th ; for round down we mean that @xmath57 is ranked in the @xmath14 group ( i.e. , @xmath57 is followed by @xmath124 groups ) . using a similar argument to the proof of lemma  6.6 from brandt et al .   with @xmath116 as described above we can reach a contradiction . we now present the remaining p  cases , which can be seen as the with - ties analog of the p  cases of lemma  6.7 from brandt et al .  . we examine each of the cases individually . for convenience , we normalize the scoring vector so that @xmath125 . if @xmath126 then clearly the optimal action for the manipulators is to vote a total order with @xmath57 uniquely first and the remaining candidates ranked arbitrarily such that the vote is single - peaked . if @xmath127 , then , as pointed out in  @xcite , lemma 6.6 applies , which has been handled above . the last p - time case is that @xmath128 , @xmath129 , and @xmath130 . notice that when the votes are single - peaked or when they are single - plateaued then @xmath131 and @xmath132 are the only candidates that can occur last in a vote , either uniquely or tied ( except for the case where all candidates are tied , but we can easily ignore these votes since they do not change the relative scores between candidates ) . since we know from lemma  [ lem : sp - first ] that all of the manipulators can put @xmath57 strictly ranked first , we can have the following manipulator votes . * @xmath133 . * @xmath134 . * @xmath135 . notice that for all votes with @xmath57 first that @xmath136 .    for all votes , @xmath137 or @xmath138 , or @xmath131 and @xmath132 are tied for last , in which case @xmath139 ( the worst case occurs with max where they each receive a score of @xmath140 ) . so , @xmath141 . if @xmath142 , @xmath109 is the optimal manipulator vote . otherwise , @xmath143 and @xmath108 is the optimal manipulator vote . we have proven that the above cases hold for single - peaked and for single - plateaued weak orders , and it is clear that the case for single - peaked bottom orders follows from the case of single - peaked total orders ( since they are equivalent ) and it is also clear how to adapt the above arguments to hold for single - peaked top orders , and for single - plateaued top orders and bottom orders . the most surprising result in the work by menon and larson   was that the complexity of 3-candidate cwcm for elimination veto for single - peaked preferences with outside options for top orders using min is np - complete , whereas for single - peaked total orders  @xcite and even for total orders in the general case  @xcite it is in p.    @xcite @xmath1-candidate elimination veto cwcm for total orders is in p  in the unique - winner model . @xcite @xmath1-candidate elimination veto cwcm for single - peaked total orders is in p  in the unique - winner model . @xcite 3-candidate elimination veto cwcm for top orders that are single - peaked with outside options is np - complete in the unique - winner model . menon and larson   state this case as a counterexample to the conjecture by faliszewski et al .  , which states that the complexity for a natural election system will not increase when moving from the general case to the single - peaked case . ( though menon and larson do qualify that the conjecture from faliszewski et al . concerned total orders . ) however , for the standard model of single - peaked preferences and for single - plateaued preferences , elimination veto cwcm for top orders , bottom orders , and weak orders using min is in p  for any fixed number of candidates , thus the counterexample crucially relies on using a nonstandard definition . @xmath1-candidate elimination veto cwcm for single - peaked and for single - plateaued top orders , bottom orders , and weak orders using min is in p  in the unique - winner model . the proof of this theorem follows from a similar argument to the proof of the theorem for single - peaked total orders from menon and larson  . this is because that proof follows from the fact that for total orders the candidate eliminated after each round is on the leftmost or rightmost location of the axis , and the reverse of an elimination order is single - peaked with respect to the axis . it is easy to see that both of these statements also hold for single - peaked votes with ties , since the only candidates that can be vetoed in each round are still the leftmost and rightmost candidates on the axis . for single - plateaued preferences it is possible for voters with an indifference plateaued to veto more than two candidates ( after all of the candidates ranked below their indifference plateau have been eliminated ) , but it is easy to see that these votes do not affect which candidate is eliminated since all of the remaining candidates are vetoed by such voters . it is also clear that lemma  12 from coleman and teague  @xcite still holds which states that if there exists a collection of votes that can induce an elimination order , then this elimination order can be induced by all of the manipulators voting the reverse of the elimination order . so since we know that the reverse of an elimination order is single - peaked with respect to the axis , and that there are only polynomially many possible elimination orders with @xmath57 first , the manipulators simply try each elimination order with @xmath57 first . since the elimination order is always a total order , the above argument clearly holds for single - peaked and single - plateaued top orders , bottom orders , and weak orders . it is known that 3-candidate copeland@xmath2 cwcm for all rational @xmath144 is np - complete for total orders in the nonunique - winner model  @xcite , and when @xmath145 ( also known as llull ) cwcm is in p  for @xmath146  @xcite and the cases for @xmath147 remain open . fitzsimmons and hemaspaandra   showed that the np - completeness of the 3-candidate case holds for top orders , bottom orders , and weak orders , and menon and larson   independently showed the top - order case . fitzsimmons and hemaspaandra   also showed that 3-candidate llull cwcm is in p  for top orders , bottom orders , and weak orders . recall that weak condorcet winners always exist when preferences are single - peaked with ties , and when they are single - plateaued . so the results that llull cwcm for single - peaked total orders is in p  from brandt et al .   also holds for the case of single - peaked and single - plateaued top orders , bottom orders , and weak orders . copeland@xmath2 for @xmath144 was shown to be in p  by yang   for single - peaked total orders . @xcite [ t : yang ] copeland@xmath2 cwcm for @xmath144 is in p   for single - peaked total orders . in contrast , for top orders that are single - peaked with outside options , it is np - complete even for three candidates  @xcite . @xcite 3-candidate copeland@xmath2 cwcm for @xmath144 is np - complete for top orders that are single - peaked with outside options .    for single - peaked and single - plateaued weak orders , bottom orders , and top orders we again inherit the behavior of single - peaked total orders . copeland@xmath2 cwcm for @xmath144 is in p  for single - peaked and single - plateaued top orders , bottom orders , and weak orders . let @xmath65 be our axis . consider a set of nonmanipulators with single - plateaued weak orders . replace each nonmanipulator @xmath66 of weight @xmath9 with two nonmanipulators @xmath148 and @xmath149 of weight @xmath9 . the first nonmanipulator breaks the ties in the vote in increasing order of @xmath65 and the second nonmanipulator breaks the ties in the vote in decreasing order of @xmath65 , i.e. , if @xmath150 and @xmath151 , then @xmath152 and @xmath153 . note that @xmath148 and @xmath149 are single - peaked total orders and that the weighted majority graph induced by the nonmanipulators after replacement can be obtained from the weighted majority graph induced by the original nonmanipulators by multiplying each weight in the graph by 2 . when we also multiply the manipulator weights by 2 , we have an equivalent copeland@xmath2 cwcm problem , where all nonmanipulators are single - peaked total orders and all manipulators have even weight . suppose @xmath57 can be made a winner by having the manipulators cast single - plateaued votes with ties . now replace each manipulator of weight @xmath154 by two weight-@xmath9 manipulators . the first manipulator breaks the ties in the vote in increasing order of @xmath65 and the second manipulator breaks the ties in the vote in decreasing order of @xmath65 . now the replaced manipulator votes are single - peaked total orders and @xmath57 is still a winner . we need the following fact from the proof of theorem  [ t : yang ] : _ if @xmath57 can be made a winner in the single - peaked total order case , then @xmath57 can be made a winner by having all manipulators cast the same p - time computable vote . _ it follows that @xmath57 can be made a winner by having all replaced manipulators cast the same single - peaked total order vote . but then @xmath57 can be made a winner by having all original manipulators cast the same single - peaked total order vote . since this vote is p - time computable , it follows that copeland@xmath2 cwcm for @xmath144 is in p  for single - plateaued weak orders , and this also holds for single - peaked weak orders since every single - peaked profile of weak orders is also single - plateaued . it is clear to see that similar arguments hold for single - peaked top orders , and for single - plateaued top orders and bottom orders . the case for single - peaked bottom orders follows from the case for single - peaked total orders . recall from lemma  [ lem : sp - first ] that for all our single - peaked models and all our scoring rule extensions , we can assume that all manipulators rank @xmath57 uniquely first . when given an axis where the preferred candidate is in the leftmost or rightmost location , there is exactly one single - peaked total order vote that puts @xmath57 first , namely , @xmath57 followed by the remaining candidates on the axis in order . this is also the case for single - peaked and single - plateaued orders with ties , since @xmath57 is ranked uniquely first and no two candidates can be tied on the same side of the peak . it follows that the weighted manipulation problems for scoring rules for single - peaked total orders and single - peaked and single - plateaued orders with ties are in p for axes where @xmath57 is in the leftmost / rightmost position . however , this is not the case when preferences with ties are single - peaked with outside options or possibly single - peaked . in case  1 of the proof of theorem  1 in the work by menon and larson  , an axis of @xmath155 is used to show np - hardness for their model . it is attractive to conjecture that for single - peaked and single - plateaued preferences , the less symmetrical ( with respect to @xmath57 ) the axis is , the easier the complexity of manipulation , but surprisingly this turns out to not be the case , even for total orders .    for the theorem stated below let @xmath156 and @xmath157 denote the number of candidates to the left and to the right on the axis with respect to the preferred candidate of the manipulators .    for single - peaked total orders , single - peaked weak orders , and single - plateaued weak orders , @xmath158 cwcm is in p  for @xmath159 and np - complete for @xmath160 and @xmath161 for all our scoring rule extensions . @xmath162 : careful inspection of the proof of lemma  6.6 from brandt et al .   proves the following refined version of that lemma that takes the axis into account . [ l : sp2p ] let @xmath163 be a scoring rule . if for all @xmath164 such that @xmath165 and @xmath166 , it holds that @xmath167 then @xmath44-cwcm for single - peaked total orders for this axis is in p.    note that lemma  [ l : sp2p ] applies in our case , since for all @xmath164 such that @xmath168 and @xmath169 , the following hold . [ cols="^,^,^,^,^ " , ]     it follows that @xmath158 cwcm is in p for single - peaked total orders when @xmath159 . it follows from the arguments in the proof of theorem  [ thm : noninc ] that @xmath158 cwcm is also in p for single - peaked and single - plateaued orders with ties for @xmath159 .    to get np - completeness for the single - peaked and single - plateaued weak order cases for all our scoring rule extensions , we need to modify the proof for single - peaked total orders . careful inspection of the proof of lemma  6.4 from brandt et al .   allows us to extract the following reduction from partition to @xmath158 cwcm for total orders that are single - peaked with respect to axis @xmath170 . given an instance of partition , a collection of @xmath59 positive integers @xmath60 such that @xmath61 , we are asking whether there exists a partition of this collection , i.e. , whether there exists a subcollection that sums to @xmath171 . the set @xmath54 of nonmanipulators consists of    * one weight @xmath172 voter voting : @xmath173 . * one weight @xmath174 voter voting : @xmath175 . the weights of the manipulators are @xmath176 . if there exists a partition , then let the set @xmath55 of manipulators vote the following . * coalition of weight @xmath177 manipulators vote @xmath178 . * coalition of weight @xmath177 manipulators vote @xmath179 . then @xmath180 , and the scores of the other candidates are lower . for the converse , note that the optimal total order votes for the manipulators are @xmath178 and @xmath181 . simple calculation shows that in order to make @xmath57 a winner , exactly half of the manipulator weight needs to vote @xmath178 . this corresponds to a partition .    for the single - peaked and single - plateaued cases for votes with ties , note that by lemma  [ lem : sp - first ] , we can assume that all manipulators rank @xmath57 uniquely first . we will look at each of our scoring extensions : max , min , average , and round down .    for max , if the manipulators can make @xmath57 a winner , we break the ties of the manipulators such that the resulting votes become total single - peaked orders . @xmath57 will still be a winner in the resulting election . this implies that the construction above also gives np - completeness for single - peaked votes with ties using max .    for round down , the construction above also works . suppose @xmath57 can be made a winner . again , we assume that all manipulators rank @xmath57 uniquely first . now replace all votes with ties ( i.e. , @xmath182 , @xmath183 , and @xmath184 ) by @xmath181 . note that @xmath185 and @xmath186 do not decrease , and so @xmath57 is still a winner of the resulting election , in which all manipulators vote a single - peaked total order . this implies that the construction above also gives np - completeness for single - peaked votes with ties using round down . for average , the construction above also works , though the proof needs a little more work . suppose @xmath57 can be made a winner . again , we assume that all manipulators rank @xmath57 uniquely first . so , @xmath187 . the optimal manipulator votes are : @xmath178 , @xmath181 , and @xmath188 . assume that these are the only manipulator votes and let @xmath189 , @xmath190 , and @xmath191 be the total manipulator weight voting each of these three votes , respectively . since @xmath57 is a winner , @xmath192 and @xmath193 . it follows that @xmath194 , @xmath195 , and @xmath196 . standard calculation shows that this implies that @xmath197 , @xmath198 and @xmath199 . thus the weights of the voters voting @xmath178 correspond to a partition .    for min , the optimal votes for the manipulators are @xmath188 and @xmath181 . in order to make the argument from the total order case work , we need to adjust the weights of the nonmanipulators a bit . namely , we let the set @xmath54 of nonmanipulators consist of    * one weight @xmath200 voter voting : @xmath173 . * one weight @xmath201 voter voting : @xmath175 . the weights of the manipulators are unchanged , i.e. , @xmath202 . note that if half the manipulator weight votes @xmath188 and remaining manipulators vote @xmath181 , then @xmath203 , @xmath204 , and @xmath205 . the scores of @xmath206 and @xmath207 are lower . similarly to the previous cases , if @xmath57 can be made a winner then standard calculations show that exactly half of the manipulator weight votes @xmath188 , which corresponds to a partition . the work by menon and larson   on the complexity of manipulation and bribery for single - peaked preferences with outside options for top orders is the most closely related to this paper . for manipulation , they show that for single - peaked preferences with outside options the complexity often increases when moving from total orders to top orders . they additionally considered a notion of nearly single - peakedness . we instead study the complexity of weighted manipulation for the standard model of single - peaked preferences with ties and for single - plateaued preferences with ties . the focus of our paper is on the computational aspects of models of single - peaked preferences with ties . these models can also be compared based on which social - choice properties that they have , such as the guarantee of a weak condorcet winner . barber   compares such properties of the models of single - peaked , single - plateaued , and single - peaked with outside options for votes with ties . since single - peakedness is a strong restriction on preferences , in real - world scenarios it is likely that voters may only have nearly single - peaked preferences , where different distance measures to a single - peaked profile are considered . both the computational complexity of different manipulative attacks  @xcite and detecting when a given profile is nearly single - peaked  @xcite have been considered . an important computational problem for single - peakedness is determining the axis given a preference profile , this is known as its consistency problem . single - peaked consistency for total orders was first shown to be in p  by bartholdi and trick  . doignon and falmagne   and escoffier , lang , and ztrk   independently found faster direct algorithms . lackner   proved that possibly single - peaked consistency for top orders is in p  ( and for local weak orders and partial orders is np - complete ) , and fitzsimmons   later showed that single - peaked , single - plateaued , and possibly single - peaked consistency for weak orders is in p. the standard model of single - peakedness is naturally defined for votes with ties , but different extensions have been considered . in contrast to recent work that studies the models of possibly single - peaked and single - peaked preferences with outside options and finds an anomalous increase in complexity compared to the tie - free case , we find that for scoring rules and other important natural systems , the complexity of weighted manipulation does not increase when moving from total orders to votes with ties in the standard single - peaked and in the single - plateaued cases . single - peaked and single - plateaued preferences for votes with ties also retain the important social - choice property of the existence of weak condorcet winners . this is not to say that possibly single - peaked and single - peaked preferences with outside options are without merit , since they both model easily understood structure in preferences . * acknowledgments : * we thank the anonymous referees for their helpful comments . this work was supported in part by nsf grant no . ccf-1101452 and a nsf graduate research fellowship under nsf grant no .  dge-1102937 .
single - peakedness is one of the most important and well - known domain restrictions on preferences . 
 the computational study of single - peaked electorates has largely been restricted to elections with tie - free votes , and recent work that studies the computational complexity of manipulative attacks for single - peaked elections for votes with ties has been restricted to nonstandard models of single - peaked preferences for top orders . 
 we study the computational complexity of manipulation for votes with ties for the standard model of single - peaked preferences and for single - plateaued preferences . 
 we show that these models avoid the anomalous complexity behavior exhibited by the other models . 
 we also state a surprising result on the relation between the societal axis and the complexity of manipulation for single - peaked preferences .