You are an expert at summarizing long articles. Proceed to summarize the following text: 
in a departure from classical voting theory , a growing literature from computational social choice has recently studied _ multi - winner _ voting rules : given diverse preferences of a collection of agents , instead of identifying a single best alternative , we are aiming for a ( fixed - size ) _ set _ of alternatives that jointly are able to represent the preferences of the agents best . such procedures are useful in a wide variety of circumstances : obvious examples include the election of a parliament , or of a committee representing the interests of members of an organisation . other applications can be found in group recommendation systems , or for making decisions about which products or services to offer : which courses should be offered at a university ? which movies should be presented on an airline entertainment system ?    several attractive rules for such tasks have been designed by researchers in political science ( e.g. , @xcite @xcite , @xcite @xcite ) and more recently by computer scientists @xcite . many of these rules are defined in terms of some objective function : a winning committee is a set of @xmath0 candidates that maximises this objective . unsurprisingly , then , the winner determination problems of such rules are typically np - hard @xcite . to tackle the complexity of these problems , approximation algorithms @xcite and fixed - parameter tractability approaches @xcite have been developed for these problems , and integer programming formulations have also been designed for them @xcite . another approach to efficiently solving these winner determination problems seeks to exploit underlying structure in the preferences reported by the agents @xcite . a particularly popular _ preference restriction _ in this space is the notion of _ single - peaked preferences _ , due to @xcite and @xcite . under this model , the alternative space has a one - dimensional structure : alternatives are ordered on a left - to - right _ axis _ ; and agents preferences are monotonically decreasing as we move further away from their _ peak _ ( most - preferred alternative ) . in particular , we can expect preferences to be structured this way when voting over the value of a numerical quantity ( such as a tax rate ) . while single - peaked preferences were first employed to escape impossibility results in social choice theory @xcite , it also yields positive algorithmic results : notably , @xcite showed that chamberlin courant s committee selection rule can be computed efficiently when preferences are single - peaked . these results can be extended to other multi - winner voting rules @xcite , and to other preference restriction such as single - crossing preferences , or single - peakedness on trees @xcite . the algorithms mentioned all directly exploit the underlying structure of the preferences . for example , the algorithm due to betzler et al . proceeds by dynamic programming along the single - peaked axis . thus , to use this algorithm , we first need a procedure to uncover this axis . fortunately , efficient recognition algorithms for the mentioned domains are known ; in particular , a suitable axis can be found in linear time @xcite . thus , the approach to tractability via preference restrictions would look roughly like shown in : given input preferences , apply recognition algorithms for several preference restrictions , and if any of these tests succeed , use a special - purpose algorithm that performs well when preferences have the uncovered structure . if none of the tests succeed , fall back to some ( superpolynomial ) general - purpose solver , such as an integer programming solver . but there is something awkward about linking together this cacophony of algorithms : given the amazing progress in solver technology in recent decades ( such as witnessed in sat competitions or in commercial ip solvers ) , it might well be faster in practice to skip these intermediate steps and go straight to cplex . ( this objection becomes stronger once implementation effort is factored in . ) further , modern ip solvers are often able to exploit underlying structure automatically : experimentally , solving times on single - peaked instances are much faster than on random instances . while such an experimental result is nice , performance guarantees are better . could it be that , on certain single - peaked instances , an ip solver performs exponentially worse than special - purpose algorithms ? the answer is no . this paper shows that integer programming solvers will _ provably _ terminate in polynomial time when solving certain voting problems on single - peaked inputs . in more detail , for several voting rules ( including chamberlin  courant and proportional approval voting ) , we will design ip formulations which are solved optimally by their lp relaxation when the preference input happens to be single - peaked . since all standard ip solvers first solve the lp relaxation , they will terminate with the correct answer in their first iteration . if the instance is not single - peaked , the ip solver might enter further iterations while solving importantly , our formulations are correct whether or not the input is single - peaked . moreover , this approach to achieving polynomial time efficiency does not require separately running a recognition algorithm ! the ip solver need not know an underlying axis , or even whether the input is single - peaked at all ; the lp relaxation will just ` magically ' have an integral solution . our proofs rely on establishing that the constraint matrices become totally unimodular in the single - peaked case . previous applications of this technique include certain tractable cases of the winner determination problems of combinatorial auctions ( see @xcite @xcite ) . our method also allows us to show that a conjecture due to @xcite is false . they consider structure in _ dichotomous preferences _ based on approval ballots , where agents only submit a binary yes / no decision for every candidate . in particular , they consider an analogue of single - peakedness in this setting ( which they call _ candidate interval _ or _ ci _ ) , which requires there to be an ordering ( axis ) of the candidates such that , for every voter , their set of approved candidates forms an interval of the axis . they then analyse an axiomatically particularly attractive multi - winner rule for the approval setting , known as proportional approval voting ( pav ) . while @xcite showed that pav is efficiently computable for a certain subclass of their ci concept , and obtained fpt results for ci preferences , they conjectured that pav remains np - hard for ci preferences in general . this conjecture appears to be largely based on the difficulty of solving this problem using dynamic programming approaches that typically work in single - peaked settings . our method , on the other hand , allows us to find a polynomial - time algorithm for this case , via ip solving . we then combine the approaches for chamberlin  courant and pav to give a similar polynomial time result for so - called owa - based multi - winner rules in the case that preferences are single - peaked . we further give an ip formulation that computes young s voting rule efficiently for single-_crossing _ preferences , and close by briefly sketching applications of our method to some further rules and settings . * total unimodularity * a matrix @xmath1 with @xmath2 is called _ totally unimodular _ if every square submatrix @xmath3 of @xmath4 has @xmath5 . the following results are well - known . proofs and much more about their theory can be found in the textbook by @xcite . [ thm : tum - is - easy ] suppose @xmath6 is a totally unimodular matrix , @xmath7 is an integral vector of right - hand sides , and @xmath8 is an objective vector . then the linear program @xmath9 has an integral optimum solution , which is a vertex of the polyhedron @xmath10 . thus , the integer linear program @xmath11 can be solved using its linear programming relaxation ( p ) . an optimum solution to ( ip ) can be found in polynomial time . we will now state some elementary results about totally unimodular matrices . [ prop : tum - manipulations ] if @xmath4 is totally unimodular , then so is    1 . its transpose @xmath12 , 2 .   the matrix @xmath13 $ ] obtained from @xmath4 by appending the negated columns of @xmath4 , 3 .   the matrix @xmath14 $ ] where @xmath15 is the identity matrix , 4 .   any matrix obtained from @xmath4 through permuting or deleting rows or columns .    in particular , from ( 3 ) and ( 4 ) it follows that appending a unit column @xmath16 will not destroy total unimodularity . further , using these transformations , we can see that remains true even if we add to ( p ) constraints giving lower and upper bounds to some variables , if we replace some of the inequality constraints by equality constraints , or change the direction of an inequality . r0.23    a binary matrix @xmath17 has the _ strong consecutive ones property _ if the @xmath18-entries of each row form a contiguous block , as in the example on the right . a binary matrix has the _ consecutive ones property _ if its columns can be permuted so that the resulting matrix has the strong consecutive ones property . every binary matrix with the consecutive ones property is totally unimodular .    by a celebrated result of @xcite , it is possible to decide in polynomial time whether a given matrix is totally unimodular . + * * single - peaked preferences**let @xmath4 be a finite set of _ alternatives _ , or _ candidates _ , and let @xmath19 . a _ weak order _ , or _ preference relation _ , is a binary relation @xmath20 over @xmath4 that is complete and transitive . we write @xmath21 and @xmath22 for the strict and indifference parts of @xmath20 . a _ linear order _ is a weak order that , in addition , is antisymmetric , so that @xmath23 only if @xmath24 . every preference relation @xmath20 induces a partition of @xmath4 into indifference classes @xmath25 so that @xmath26 and @xmath27 for all @xmath28 . we will say that an alternative @xmath29 has _ rank _ @xmath30 in the ordering @xmath20 and write @xmath31 ; thus the alternatives of rank 1 are the most - preferred alternatives under @xmath20 . finally , we say that any set of the form @xmath32 is a _ top - inital segment _ of @xmath20 . r0.4    let @xmath33 be ( the strict part of ) a linear order over @xmath4 ; we call @xmath33 an _ axis_. a linear order @xmath34 with most - preferred alternative @xmath35 ( the _ peak _ ) is _ single - peaked with respect to @xmath33 _ if for every pair of candidates @xmath36 with @xmath37 or @xmath38 it holds that @xmath39 . for example , if the alternatives in @xmath4 correspond to different proposed levels of a tax , and the numbers in @xmath4 are ordered by @xmath33 in increasing order , then it is sensible to expect voters preferences over @xmath4 to be single - peaked with respect to @xmath33 . note that @xmath21 is single - peaked with respect to @xmath33 if and only if all top - initial segments of @xmath21 form an interval of @xmath33 . accordingly , we will define a _ weak _ order @xmath20 to be _ single - peaked _ with respect to @xmath33 exactly if all top - initial segments of @xmath20 form an interval of @xmath33 . this concept is often known as ` possibly single - peaked ' @xcite because it is equivalent to asking that all the ties in the weak order can be broken in such a way that the resulting linear order is single - peaked .    a _ profile _ @xmath40 over a set of alternatives  @xmath4 is a list of weak orders over @xmath4 . each of the orders represents the preferences of a _ voter _ ; we write @xmath41 $ ] for the set of voters . the profile will be called _ single - peaked _ if there exists some axis @xmath33 over @xmath4 so that each order @xmath42 in @xmath43 is single - peaked with respect to @xmath33 . a profile is single - peaked if and only if the following matrix @xmath44 has the consecutive ones property : take one column for each alternative , and one row for each top - initial segment @xmath45 of each voter s preference relation ; the row is just the incidence vector of @xmath45 . this construction is due to @xcite . + * * dichotomous preferences**a weak order @xmath20 is _ dichotomous _ if it partitions @xmath4 into at most two indifference classes @xmath46 . the alternatives in @xmath47 are said to be _ approved _ by the voter @xmath20 . on dichotomous preferences , the notion of single - peakedness essentially coincides with the consecutive ones property @xcite : there needs to be an ordering @xmath33 of the alternative so that each approval set @xmath47 is an interval of @xmath33 . thus , @xcite use the name _ candidate interval ( ci ) _ for single - peakedness in this context . +    r0.265    * * single - crossing preferences**a profile @xmath48 of _ linear _ orders is called single - crossing if voters can be ordered so that for all @xmath36 , the set of voters who prefer @xmath49 to @xmath50 form an interval of this ordering . again , this can be phrased in terms of the consecutive ones property of a matrix @xmath51 built from the profile : take one column for each voter , and one row for each of the @xmath52 pairs @xmath36 ; there is a 1 in this row for each voter with @xmath53 . in this section , we will consider proportional approval voting ( pav ) , a multiwinner voting rule defined for dichotomous ( approval ) preferences . a nave way to form a committee would be to select the @xmath0 alternatives with highest approval score , but this method tends to ignore minority candidates , and so is not representative @xcite . pav attempts to fix this issue . the rule appears to have been first proposed by @xcite . in the general case , a winning committee under pav is hard to compute @xcite . let us define pav formally . each voter @xmath54 submits a set @xmath55 of _ approved _ candidates ( or , equivalently , a dichotomous weak order with @xmath56 ) . we aim to find a good committee @xmath57 of size @xmath58 . the intuition behind proportional approval voting ( pav ) is that voters are happier with committees that contain more of their approved candidates , but that there are decreasing marginal returns to extra approved candidates in the committee . concretely , each voter obtains a ` utility ' of 1 for the first approved candidate in @xmath59 , of @xmath60 for the second , of @xmath61 for the third , and so on . the objective value of a committee @xmath57 is thus @xmath62 the choice of harmonic numbers might seem unusual , and one can more generally define a rule @xmath63  where @xmath64 is a non - increasing scoring vector ( so @xmath65 when @xmath66 ) . this rule gives @xmath59 the objective value @xmath67 . then pav is just @xmath68-pav . however , the choice of harmonic numbers is the only vector @xmath69 that lets @xmath63  satisfy an axiom called ` extended justified representation ' @xcite , making this a natural choice after all . let us now analyse our first ip formulation , for pav . @xmath70 } \alpha_\ell \cdot x_{i,\ell } } & & \multicolumn{2}{r}{\text{(pav - ip ) } } \\    \text{subject to }     & \displaystyle\sum_{c\in c } y_{c\hphantom{,\ell } } & = & k & & & \text{(2 ) } \\    & \displaystyle\sum_{\ell \in [ k ] } x_{i,\ell } & { \leqslant } & \displaystyle\sum_{\mathclap{i \text { approves } c } } \ : y_c & & \text{for } i \in n & \text{(3 ) } \\    & x_{i,\ell } & \in & \{0,1\ } & & \text{for } i\in n,\ : \ell\in[k ] & \text{(4 ) } \\    & y_{c\hphantom{,\ell } } & \in & \{0,1\ } & & \text{for } c\in c \end{array}\ ] ]    program correctly computes an optimal committee according to @xmath63 .    in any feasible solution of , the variables @xmath71 encode a committee of size @xmath0 . fix such a committee fix such a committee @xmath72 . we show that in optimum , the objective value of the solution is the @xmath63-value of this committee .    since @xmath73 , in optimum , as many @xmath74 will be set to 1 as constraint ( 3 ) allows . thus , for each @xmath54 , exactly @xmath75 many variables @xmath76 will be set to 1 . since @xmath77 is non - increasing , wlog , in optimum , these will be variables @xmath78 . then the objective value equals the @xmath63-value of @xmath59 .    an interesting feature of ( pav - ip ) is that the integrality constraints ( 4 ) on the variables @xmath74 can be relaxed to just @xmath79 ; this does not change the objective value of the optimum solution . this is because ( a ) in optimum , the quantity @xmath80 is integral and ( b ) it never pays to then have one of the @xmath76 to be fractional , because this fractional amount can be shifted to @xmath81 with ( weakly ) higher value . this observation might tell us that solving ( pav - ip ) is relatively easy as it is `` close '' to being an lp , and this also seems to be true in practice . on the other hand , it is not necessarily beneficial to relax the integrality constraints ( 4 ) when passing ( pav - ip ) to an ip solver : the presence of integrality constraints might nudge the solver to keep numerical integrality gaps smaller .    of course , the point of this paper is to give another reason why ( pav - ip ) is `` close '' to being an lp . [ prop : pav - tum ] the constraint matrix of is totally unimodular when the input preferences are single - peaked .    we will use the manipulations allowed by proposition  [ prop : tum - manipulations ] liberally . in particular , it allows us to ignore the constraints @xmath82 , and to ignore the difference between equality and inequality constraints . thus , after permuting columns corresponding to variables @xmath76 so that they are sorted by @xmath54 , the constraint matrix of ( pav - ip ) is @xmath83[l]{$\smash{\overbrace{\phantom {                     \begin{matrix}-i_n & \dots & -i_n\end{matrix}}}^{\text{$k$ times}}}$}-i_n & \dots & -i_n } & m_{\text{sp}}^p \\ \mathbf 0_n & \dots & \mathbf 0_n & \mathbf 1_m      \end{bmatrix}.\ ] ] if preferences @xmath43 are single - peaked , then @xmath44 has the consecutive ones property , and this is also true after appending a row with all-1s . thus , @xmath84 $ ] is totally unimodular . applying proposition  [ prop : tum - manipulations ] repeatedly to append negations of unit columns , we obtain @xmath85 , which is thus totally unimodular . using , we obtain our desired result . @xmath63  can be computed in polynomial time for single - peaked approval preferences . now we leave the domain of dichotomous preferences , and consider the full generality of profiles of weak orders . the definition of chamberlin courant s rule is based on the notion of having a _ representative _ in the elected committee : each voter is represented by their favourite candidate in the committee , and voters are happier with more preferred representatives . let @xmath86 be a ( non - increasing ) scoring vector ; the standard choice for @xmath77 are borda scores : @xmath87 . let @xmath88 be a profile . then the objective value of a committee @xmath57 according to chamberlin courant s rule is @xmath89 chamberlin  courant now returns any committee @xmath57 with @xmath58 that maximises this objective . the rule thus defined can be seen as a ( non - metric ) facility location problem : each candidate @xmath90 is a potential facility location , we are allowed to open exactly @xmath0 facilities , and the distance between customers and facilities are determined through @xmath77 . there is a standard integer programming formulation for this problem using binary variables @xmath71 , denoting whether @xmath91 will be opened or not , and variables @xmath92 , denoting whether facility @xmath91 will service voter @xmath54 . we will need an alternative formulation based on maximising a number of _ points_. for expositional simplicity , let s take @xmath77 to be borda scores ; other scoring rules can be obtained by weighting the points . here is another way of thinking about the objective value as defined above : each voter @xmath54 can earn a point for each _ rank _ in @xmath54 s preference order : for every rank @xmath93 $ ] , @xmath54 earns the point @xmath94 if there is a committee member @xmath95 with @xmath96 . then the number of points obtained in total equals the objective values : if @xmath54 s favourite committee member is in rank @xmath97 , then @xmath54 will earn precisely @xmath98 points , namely the points @xmath99 . this view suggests the following integer programming formulation , where we put @xmath100 and @xmath101 . @xmath102 }   w'_r \cdot x_{i , r } }   & & \multicolumn{2}{r}{\text{(cc - ip ) } } \\ \text{subject to }   & \displaystyle\sum_{c\in c } y_{c } & = & k & & & \text{(2 ) } \\ & x_{i , r } & { \leqslant } & \displaystyle\sum_{\mathclap{c \ : : \ : { \textrm{rank}}(c ) { \geqslant}r } } \ : y_c & & \text{for } i \in n,\ : r\in[m ] & \text{(3)}\\ & x_{i , r } & \in & \{0,1\ } & & \text{for } i\in n,\ : r\in[m ] \\ & y_{c\hphantom{,\ell } } & \in & \{0,1\ } & & \text{for } c\in c \end{array}\ ] ]    program correctly computes an optimal committee according to @xmath77-chamberlin  courant .    in any feasible solution of , the variables @xmath71 encode a committee of size @xmath0 . fix such a committee @xmath72 . we show that in optimum , the objective value of the solution is the objective value of this committee according to @xmath77-cc .    since @xmath103 , in optimum , every @xmath94 will be set to @xmath18 if constraint ( 3 ) allows this . this is the case iff there is a committee member @xmath95 with @xmath96 , i.e. , iff the ` point ' @xmath94 is earned as described above . then it is clear that the objective of ( cc - ip ) corresponds to chamberlin courant s objective . the constraint matrix of is totally unimodular when the input preferences are single - peaked . after similar simplification as in proposition  [ prop : pav - tum ] we see that the constraint matrix of ( cc - ip ) is @xmath104 again , if preferences @xmath43 are single - peaked , then @xmath44 has the consecutive ones property , and this is also true after appending a row with all-1s . thus , @xmath84 $ ] is totally unimodular . applying proposition  [ prop : tum - manipulations ] repeatedly to append unit columns , we obtain @xmath105 , which is thus totally unimodular . chamberlin  courant with score vector @xmath77 can be solved in polynomial time for single - peaked preferences . in the philosophy behind chamberlin  courant , each voter is represented by exactly one committee member , and obtains all ` utility ' through this representation . in many application scenarios , we may instead seek _ multirepresentation _ @xcite : for example , you might watch several of the movies offered by an inflight - entertainment system . in such scenarios , chamberlin  courant might design a suboptimal committee ; skowron et al . introduce _ owa - based _ multiwinner rules as a more flexible alternative ( see also @xcite @xcite ) .    given a vector @xmath106 , a weight vector @xmath107 defines an _ ordered weighted average _ ( owa ) operator as follows : first , sort the entries of @xmath108 into non - increasing order , so that @xmath109 ; second , apply the weights : the ordered weighted average of @xmath108 with weights @xmath110 is given by @xmath111 . for example , @xmath112 gives the maximum , and @xmath113 gives the sum of the numbers in @xmath108 . now , a scoring vector @xmath86 and an owa @xmath69 define an owa - based multi - winner rule as follows : given a profile  @xmath43 , the rule outputs a committee @xmath114 that maximises the objective value @xmath115 thus , choosing @xmath116 gives us @xmath77-chamberlin  courant as a special case . choosing @xmath117 gives us an analogue of chamberlin  courant where voters are represented by their favourite _ two _ members of the committee . the owa - based rules with @xmath118 and @xmath119 gives us pav , when given dichotomous preferences as input . thus , owa - based rules generalise both chamberlin  courant and pav , and it turns out that we can apply our method to these rules by merging the ideas of ( pav - ip ) and ( cc - ip ) . however , our formulation is only valid for _ non - increasing _ owa vectors with @xmath65 whenever @xmath66 . thus , for example , we exclude the rule where voters are represented by their _ least_-favourite committee member . that are zero except for constantly many values at the end . ]    for the ip , we again put @xmath100 and @xmath101 . @xmath120 } } \sum_{\ell \in [ k ] } \sum_{r\in [ m ] } \alpha_\ell \cdot w_r ' \cdot x_{i,\ell , r } \hfill \text{(owa - ip ) } } \\ \text{subject to }   & \displaystyle\sum_{c\in c } y_{c\hphantom{,\ell , r } } & = & k & & & \text{(2 ) } \\ & \displaystyle\sum_{\ell \in [ k ] } x_{i,\ell , r } & { \leqslant } & \displaystyle\sum_{\mathclap{c \ : : \ : { \textrm{rank}}(c ) { \geqslant}r } } \ : y_c & & \text{for } i \in n,\ : r\in[m ] & \text{(3)}\\ & x_{i,\ell , r } & \in & \{0,1\ } & & \text{for } i\in n,\ : \ell , \ : r & \text{(4 ) } \\ & y_{c\hphantom{,\ell , r } } & \in & \{0,1\ } & & \text{for } c\in c \end{array}\ ] ]    if @xmath69 and @xmath77 are non - increasing , correctly computes an optimal committee according to the owa - based rule based on @xmath69 and @xmath77 . similarly to previous arguments , in optimum , we will have @xmath121 if and only if the committee @xmath72 contains at least @xmath122 candidates that voter @xmath54 ranks in rank @xmath97 or above . thus , the objective value of ( owa - ip ) agrees with the defined objective of the owa - based rule . the following property is proved very similarly to before . the constraint matrix of is totally unimodular when input preferences are single - peaked . owa - based rules with non - increasing owa operator can be solved in polynomial time for single - peaked preferences . in contrast to the rules we have considered so far , young s voting rule does not select a committee ; it is a _ single_-winner voting rule that is based on extending condorcet s rule . given a profile @xmath43 , an alternative @xmath90 is a _ condorcet winner _ if it beats every other alternative in a pairwise majority contest , i.e. , for every @xmath123 , the number of voters in @xmath43 with @xmath124 strictly exceeds the number of voters with @xmath125 ( thus defined , condorcet winners are unique ) . as is well - known , not every profile admits a condorcet winner . how should we choose the outcome in such profiles ? young s rule chooses the condorcet winners of the largest subprofiles that do admit a condorcet winner , where a subprofile can be obtained by _ deleting voters_. in other words , young s rule yields all alternatives that can be made condorcet winners by deleting a minimum number of voters . young s rule also assigns to each alternative @xmath91 a _ score _ , namely the number of voters in a maximum subprofile of @xmath43 in which @xmath91 is the condorcet winner ; young winners are the alternatives with maximum score . deciding whether a given alternative is a young winner is @xmath126-complete @xcite , but is solvable in polynomial time for single - peaked @xcite and single - crossing preferences , essentially because such profiles always admit a condorcet winner ( in odd electorates ) . since , in general , it is hard to find a young winner , it is also hard to find the young _ score _ of a given alternative @xmath49 . this latter problem admits the following simple ip formulation . here , the variables @xmath127 indicate whether voter @xmath54 is to be deleted from the profile , and @xmath128 is the _ majority margin _ of @xmath50 over @xmath49 . @xmath129    while previous ips were easy for single - peaked profiles , this one behaves nicely for single-_crossing _ preferences :    the constraint matrix of is totally unimodular when input preferences are single - crossing .    after disregarding the constraints @xmath130 , the constraint matrix is a submatrix of @xmath51 , consisting of just the rows corresponding to pairs @xmath131 for @xmath132 . if input preferences are single - crossing , then @xmath51 has the consecutive ones property , and hence so do all its submatrices . it follows that young scores can be computed in polynomial time when preferences are single - crossing . this in itself is not an impressive result , since there is a very easy direct algorithm for solving this special case , on top the median yields the young score of @xmath49 . see also @xcite . ] but the advantage of the method via integer programming is that we need not check whether @xmath43 is single - crossing or not to obtain the efficiency gains . * more than single - peakedness . * our polynomial - time results apply to a slightly larger class than just single - peaked profiles : they also apply when @xmath133 ( with an all-1s row appended ) is totally unimodular but does not necessarily have the consecutive ones property . it can be shown that this is the case whenever @xmath43 contains only two distinct voters , or , more generally , when the set of all top - initial segments of @xmath43 can also be induced by a two - voter profile . together with single - peaked profiles , we conjecture that these classes of profiles are precisely the profiles for which the relevant constraint matrices are totally unimodular . * egalitarian versions . * we can obtain egalitarian versions of the multi - winner rules that we have discussed by replacing the sum over @xmath134 by a minimum in their objective values @xcite . for pav and chamberlin  courant , our ip formulations can easily be adapted to answer the question `` is there a committee with egalitarian objective value @xmath135 ? '' while preserving total unimodularity in the case of single - peaked preferences . an optimum committee can then be found by a binary search on @xmath136 . however , it is unclear how this can be achieved for owa - based rules . it is also unclear how to handle other utility aggregation operators such as leximin ( see @xcite @xcite ) . * pav and voter intervals . * @xcite define an analogue of single - crossingness for dichotomous preferences called _ voter interval _ ( vi ) , which requires the _ transpose _ of @xmath133 to have the consecutive ones property . as for ci , they conjectured that pav remains hard on vi preferences . we could not solve this problem using our method : the constraint @xmath137 of ( pav - ip ) destroys total unimodularity . * dodgson s rule . * an alternative is a _ dodgson winner _ if it can be made a condorcet winner using a minimum number of swaps of adjacent alternatives . this number of swaps is the _ dodgson score _ of an alternative . @xcite give an ip formulation for this problem , which is also used in the treatment of @xcite . sadly , while ` most ' of the constraint matrix is again identical to @xmath133 , some extra constraints ( saying that the swaps in each vote should only count once ) destroy total unimodularity , so our method can not be employed for this formulation . note that while @xcite give an efficient algorithm for finding a dodgson _ winner _ in the case of single - peaked preferences , the problem of efficiently calculating _ scores _ appears to be open and non - trivial . maybe there is an alternative ip formulation that can be made to work using our approach .    * kemeny s rule . * @xcite present several ip formulations for kemeny s rule . the poly - size formulation they give involves constraints enforcing transitivity of the kemeny ranking ; these constraints are not totally unimodular . in any case , most strategies for calculating kemeny s rule first calculate all pairwise majority margins ; we might as well check for transitivity at this stage  trying to use fancy total unimodularity is unnecessary . aziz , h. ; brill , m. ; conitzer , v. ; elkind , e. ; freeman , r. ; and walsh , t. 2015a . justified representation in approval - based committee voting . in _ proceedings of the twenty - ninth aaai conference on artificial intelligence _ , 784790 . aaai press . bredereck , r. ; faliszewski , p. ; niedermeier , r. ; skowron , p. ; and talmon , n. 2015 . elections with few candidates : prices , weights , and covering problems . in _ international conference on algorithmic decision theory _ , 414431 . springer . caragiannis , i. ; covey , j.  a. ; feldman , m. ; homan , c.  m. ; kaklamanis , c. ; karanikolas , n. ; procaccia , a.  d. ; and rosenschein , j.  s. 2009 . on the approximability of dodgson and young elections . in _ proceedings of the twentieth annual acm - siam symposium on discrete algorithms _ , 10581067 . society for industrial and applied mathematics . elkind , e. ; lackner , m. ; and peters , d. 2016 . preference restrictions in computational social choice : recent progress . in _ proceedings of the twenty - fifth international joint conference on artificial intelligence , ijcai 2016_.      faliszewski , p. ; hemaspaandra , e. ; hemaspaandra , l.  a. ; and rothe , j. 2011 . the shield that never was : societies with single - peaked preferences are more open to manipulation and control . 209(2):89107 . faliszewski , p. ; skowron , p. ; slinko , a. ; and talmon , n. 2016a . multiwinner analogues of the plurality rule : axiomatic and algorithmic perspectives . in _ proceedings of the thirtieth aaai conference on artificial intelligence_.    faliszewski , p. ; skowron , p. ; slinko , a. ; and talmon , n. 2016b . committee scoring rules : axiomatic classification and hierarchy . in _ proceedings of the 25th international joint conference on artificial intelligence ( ijcai-2016)_.                            skowron , p. ; faliszewski , p. ; and lang , j. 2015 . finding a collective set of items : from proportional multirepresentation to group recommendation . in _ proceedings of the twenty - ninth aaai conference on artificial intelligence _ , 21312137 . aaai press .
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ many np - hard winner determination problems admit polynomial - time algorithms when restricting inputs to be single - peaked . 
 commonly , such algorithms employ dynamic programming along the underlying axis . 
 we introduce a new technique : carefully chosen integer linear programming ( ip ) formulations for certain voting problems admit an lp relaxation which is totally unimodular if preferences are single - peaked , and which thus admits an integral optimal solution . 
 this technique gives fast algorithms for finding optimal committees under the pav and chamberlin  courant voting rules under single - peaked preferences , as well as for certain owa - based rules . under single - crossing preferences , 
 young scores can also be calculated . 
 an advantage of this technique is that no special - purpose algorithm needs to be used to exploit structure in the input preferences : any standard ip solver will terminate in the first iteration if the input is single - peaked , and will continue to work otherwise . 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    = 1    @topnum0 @botnum0