Voting in Two-Crossing Elections

1 Introduction

Many impossibility results in social choice theory disappear if we assume restrictions on the voting preferences. The single-crossing domain is among the most studied restrictions in the literature. Not only does it make many social choice problems tractable, but it is also justifiable practically when placing both voters and candidates on a one-dimensional "left-right" spectrum. However, this one-dimensional model is often too restrictive, with real voting preferences hardly ever adhering to the single-crossing model. In this paper we wonder to what degree we can assume a more general model whilst preserving some of the theoretical and algorithmic properties of single-crossingness.

In multi-party democracies, one can often witness situations in which both the far left and the far right oppose against a change brought up by centrist parties. This was prominently happening during the Weimar Republic, but is common also today and known as "unholy alliance" or "The enemy of my enemy is my friend." This generalized political model is known as the horseshoe theory; if the far left and the far right are actually closer to each other than to the center, the political line bends into a horseshoe, or even a circle.

An election is single-crossing if voters can be ordered into a list such that, as we sweep from left to right, the relative order between every pair of distinct candidates changes at most once. In this paper, we generalize the single-crossing property to a two-crossing property, such that the relative order of every pair of candidates is allowed to change at most twice (Figure 1). As we shall see, this can directly model a horseshoe political system. In contrast to singlecrossing preferences, there is evidence that two-crossing preferences can accurately capture real voting behavior, particularly in economic preferences [Chen et al., 2021]. It is worth noting that single-crossing preferences were also first introduced in similar economic settings [Mirrlees, 1971; Roberts, 1977]. Beyond these practical considerations, we believe that it is worth studying more general domain restrictions, and two-crossing seems like a natural candidate.

Determining the winners of an election is perhaps the oldest and most fundamental problem in the field. In most single-winner voting systems, finding the winners is straightforward, with a few notable exceptions, for which the problem is at least NP-hard: Young [Rothe et al., 2003; Brandt et al., 2015; Fitzsimmons and Hemaspaandra, 2020], Dodgson [Bartholdi et al., 1989; Hemaspaandra et al., 1997] and Kemeny [Bartholdi et al., 1989; Hemaspaandra et al., 2005]. For single-crossing preferences, all the aforementioned admit polynomial time algorithms, hinging essentially on the existence of (weak) Condorcet winners, which are easy to compute and, at least for an odd number of voters, actually give the winner straight away. For two-crossing elections, the situation is more interesting, as we shall see.

When it comes to multi-winner rules, there are many prominent examples which are NP-hard, including one of the most studied, the Chamberlin-Courant rule for proportional representation, which is hard even when voters' dissatisfaction values follow very simple patterns [Procaccia et al., 2008; Lu and Boutilier, 2011]. On the other hand, computing a winning committee is easy for single-crossing preferences [Skowron et al., 2015; Constantinescu and Elkind, 2021], but NP-hard for three-crossing preferences [Misra et al., 2017]. Studying the two-crossing case is required to close this gap.

Our Contribution. We study two-crossing elections from an axiomatic and algorithmic point of view. Axiomatically, we show that they are equally expressive to unrestricted elections in terms of the (weighted) majority tournament: all weighted majority tournaments with same-parity weights are inducible by a two-crossing profile. Consequently, Slater, Banks, Minimal Extending Set, Tournament Equilibrium Set, Kemeny and Ranked Pairs are all NP-hard under two-crossing elections. Algorithmically, we show how recognition can be achieved in polynomial time and study the winner determination problem for Young's and the Chamberlin-Courant rule, in both cases providing polynomial time algorithms.

Full Version. The full version [Constantinescu andWattenhofer, 2022] provides the omitted proofs and a discussion of recognizing k-crossingness for general k.

2 Preliminaries

Given integer n, we write [n] for the set {1, . . . , n}; given two integers ℓ ≤ r, we write [ℓ : r] to denote the set {ℓ, . . . , r}. For a fixed n and 1 ≤ ℓ < r ≤ n we write [r : ℓ] for the set [1 : ℓ] ∪ [r : n]. A subset I ⊆ [n] is an interval if I = [ℓ : r] for some 1 ≤ ℓ ≤ r ≤ n and a circular interval if we also allow for ℓ > r in the preceding condition. For a statement S, we write [S] for the Iverson bracket: [S] = 1 if S holds, and 0 otherwise.

We consider a setting where voters V = [n] express their preferences over a set of candidates (or alternatives) C = [m]. Voters rank candidates from best to worst, so that the preferences of a voter v are given by a linear order ≻v: given two distinct candidates c, c′ ∈ C we write c ≻v c′ when v prefers c to c′ . The list of all voters' preferences is denoted by P = (≻v)v∈V , and is referred to as a preference profile. We use L(C) to denote the set of all linear orders over C, such that P ∈ L(C)n .

Pairwise Majority and Young's Rule. Given a profile P over candidate set C and two candidates c, c′ ∈ C we write nc,c′ = |{i ∈ V : c ≻i c′ }| for the number of voters who prefer c to c′ ; the so-called majority margin is then mc,c′ = nc,c′ - nc′ ,c. Consider orienting the edges of the complete graph on C such that c → c′ iff mc,c′ > 0; leaving out edges with mc,c′ = 0. This construction is known as the majority tournament of election P. If each edge c → c′ is also given weight mc,c′ , then the resulting construction is known as the weighted majority tournament of P. If there is a candidate c ∈ C such that mc,c′ > 0 for all c′ ̸= c, then c is called the strong Condorcet winner. If the previous condition is weakened to mc,c′ ≥ 0, then c is only a weak Condorcet winner, which there can be multiple of. For profile P, the strong (weak) Young score of a candidate c ∈ C is the minimum number of voters that need to be removed from P such that c becomes a strong (weak) Condorcet winner; in some cases this score will be infinite. In the strong (weak) Young's rule candidates with the smallest strong (weak) Young score are declared the winners. Traditionally, "Condorcet winner" means the strong variant, while "Young's rule" means the weak variant [Caragiannis et al., 2016].

Tournament Solutions. Under some voting rules, knowledge of the (weighted) majority tournament is enough to compute the winners; we call such rules (weighted) tournament solutions. Some tournament solutions allow for polynomial time winner determination, the most natural example being Copeland. However, for a significant number of tournament solutions it is NP-hard to determine the winners - unweighted examples: Slater, Banks, Minimal Extending Set, Tournament Equilibrium Set; weighted examples: Kemeny, Ranked Pairs. See [Brandt et al., 2016; Fischer et al., 2016] for a survey on the topic.

In what follows, we assume that we are also given a misrepresentation function ρ : V × C → Q; ρ is consistent with P if c ≻v c′ implies ρ(v, c) ≤ ρ(v, c′ ) for all v ∈ V and c, c′ ∈ C. Intuitively, the value ρ(v, c) indicates to what extent candidate c misrepresents voter v. A common example of a misrepresentation function is the Borda function ρB given by ρB(v, c) = |{c′ ∈ C : c′ ≻v c}|; this function assigns value 0 to a voter's top choice, value 1 to his second choice, and value m- 1 to his last choice.

The Chamberlin-Courant Rule. A multiwinner voting rule maps a profile P over a candidate set C, and a positive integer k ≤ |C|, to a non-empty collection of subsets of C of size at most k; 1 the elements of this collection are called the winning committees. An assignment function is a mapping w : V → C; for each V ′ ⊆ V we write w(V ′ ) = {w(v) : v ∈ V ′ } for the image of V ′ under w. If |w(V )| ≤ k, then w is called a k-assignment. Given a misrepresentation function ρ and a profile P = (≻v)v∈V , the total dissatisfaction of voters in V under a k-assignment w is given by Φρ(P,w) = ∑v∈V ρ(v,w(v)). Intuitively, w(v) is the representative of voter v in the committee w(V ), and Φρ(P,w) measures to what extent the voters are dissatisfied with their representatives. An optimal k-assignment for ρ and P is a k-assignment that minimizes Φρ(P,w) among all k-assignments for P. The Chamberlin-Courant multiwinner voting rule [Chamberlin and Courant, 1983; Faliszewski et al., 2017] maps each triple (P, ρ, k) consisting of a preference profile P = (≻v)v∈V over a candidate set C, a misrepresentation function ρ : V × C → Q that is consistent with P, and a positive integer k ≤ |C|, to all sets W such that W = w(V ) for some k-assignment w that is optimal for ρ and P, constituting the winning committees. It is NP-hard to determine whether a k-assignment of dissatisfaction Φρ(P, w) ≤ B exists for some input parameter B, even in the special cases where ρ(v, c) ∈ {0, 1} [Procaccia et al., 2008], or if ρ is the Borda function [Lu and Boutilier, 2011].

1 Usually exactly k, but in our case the difference is immaterial.

k-Crossing Preferences. A profile P = (≻v)v∈V over C is k-crossing if there is a permutation (σi)i∈V of V such that for every pair of distinct candidates (c, c′ ) ∈ C 2 the number of indices i ∈ [n - 1] such that [c ≻σi c′ ] ̸= [c ≻σi+1 c′ ] is at most k. That is, if we order the voters in V according to σ and traverse the list of voters from left to right, each pair of candidates 'crosses' at most k times. In this case we write that P is k-C, with respect to σ. A profile P is single-interval on a circle if there is a permutation (σi)i∈V such that for all pairs of distinct candidates (c, c′ ) ∈ C 2 the set {i ∈ V : c ≻σi c′ } is a circular interval over [n]. If so, we write that P is SI� on the circle induced by σ. For Φ ∈ {k-C, SI�} the recognition problem ΦREC asks: given a preference profile P, is there a permutation σ such that P is L with respect to σ? If yes, one is also interested in finding such a witnessing σ.

Lemma 1. For any permutation (σi)i∈V , profile P is twocrossing with respect to σ iff P is single-interval on the circle induced by σ. Consequently, P is two-crossing iff P is SI�.

Proof. Consider two candidates c ̸= c′ . If {i ∈ V : c ≻σi c′ } is a circular interval, then there are at most two crosses, one at each interval end. Conversely, assume there are two crosses (the cases with one/zero crosses are similar) at positions 1 ≤ i1 < i2 < n and that, without loss of generality, σ1 prefers c to c′ . Then, voters in [i1 + 1 : i2] prefer c′ to c and voters in [i2 + 1 : i1] prefer c to c′ , both being circular intervals.

Lemma 2. Consider a horseshoe political system: voters and candidates are assigned points on the unit circle, voters rank candidates in increasing order of circle arc-length distance from their assigned point, assume no ties. Then, voters' preferences are two-crossing.

The Consecutive Ones Problem. An n × m binary matrix M has the consecutive ones property if its rows can be permuted such that in each column ones form a single continuous run. In this case, we say that M is C1P. Generalizing, M is k-C1P if its rows can be permuted such that in each column ones form at most k continuous runs. Similarly, M has the circular consecutive ones property if its rows can be permuted such that in each column ones form a single continuous run if we allow loop-around; we use C1P� to denote this property. For Φ ∈ {C1P, k-C1P, C1P�} we use ΦREC to denote the corresponding recognition problems. It is instructive to note the following facts tying C1P and C1P�.

Lemma 3 ([Tucker, 1971, Theorem 1]). From a binary matrix M construct M c by flipping ones and zeros on those columns with a one in the first row of M. Then, any permutation of rows σ fixing the first row witnesses that M is C1P� iff σ witnesses that M c is C1P.

Corollary 4. C1P REC � and C1P REC are equivalent (interreducible with respect to complexity-preserving reductions). This also extends to finding witnessing permutations.

Recognizing C1P/C1P� matrices and finding witnessing permutations can both be achieved in time linear in the size of the matrix [Booth and Lueker, 1976]. A simpler O(nm2 ) algorithm was given by [Fulkerson and Gross, 1965]. For k ≥ 2, k-C1P REC is NP-complete [Goldberg et al., 1995].

3 Recognizing k-Crossing Profiles

The problem of recognizing single-crossing elections admits a number of polynomial time algorithms [Elkind et al., 2012; Bredereck et al., 2013], but, to the best of our knowledge, recognizing k-crossing profiles for k > 1 has not been studied. We prove that recognizing two-crossing profiles reduces to recognizing C1P matrices, which is tractable in poly-time.

Given a profile P over candidate set C, let MP be a binary matrix with n rows and m(m- 1) columns: one row for each voter v ∈ V and one column for each pair of distinct candidates (c, c′ ) ∈ C 2 ; such that MP[v, (c, c′ )] = [c ≻v c′ ].

Lemma 5. For any permutation (σi)i∈V , P is single-interval on the circle induced by σ iff MP is C1P� with respect to σ. Consequently, P is single-interval on a circle iff MP is C1P�.

Proof. Consider two candidates c ̸= c′ . The requirement on (c, c′ ) for SI� on the circle induced by σ to hold is that the set {i ∈ V : c ≻σi c′ } is a circular interval over [n]. This is equivalent to saying that its indicator function [c ≻σi c′ ] has all ones grouped into a single circular run, which is, by definition of MP, the same as saying that column (c, c′ ) of MP reordered by σ has all ones in a single circular interval. Quantifying over all c ̸= c′ gives the conclusion.

Theorem 6. Given a preference profile P, deciding whether it is two-crossing and, if affirmative, finding a witnessing permutation can be done in time O(nm2 ).

We note that the construction for MP was first suggested by [Bredereck et al., 2013], but their result is somewhat different: they show that P is single-crossing iff MP is C1P, while we show that P is two-crossing iff MP is C1P� (i.e. M cP is C1P). The relationship between consecutive ones and k-crossingness seems to go deeper than this. Say P is k-interval on a circle if voters can be rearranged into a circle such that for all pairs of distinct candidates (c, c′ ) ∈ C 2 the set {i ∈ V : c ≻i c′ } is a union of at most k circular intervals. Similarly, say a matrix is k-C1P� if its rows can be rearranged such that each column has at most k circular runs of ones. With these conventions, one can follow the proof of Lemma 1 to also show that P is 2k-crossing iff P is k-interval on a circle. Moreover, one can follow the proof of Lemma 5 to show that P is k-interval on a circle iff MP is k-C1P�.

4 WeightedMajority Tournaments

Single-crossing is attractive from an axiomatic standpoint: the majority relation is transitive and a Condorcet winner exists, for odd n. The Condorcet Paradox profile consists of 3 voters, so it can be easily seen as two-crossing. Therefore, Condorcet winners might not exist under two-crossing. This begs the question, can we guarantee anything about the weighted majority tournament of a two-crossing election?

The following result, similar to [Peters and Lackner, 2020] for elections single peaked on a circle, answers negatively.

Theorem 7 (Debord-McGarvey for Two-Crossing Elections). Any weighted majority tournament with weights of the same parity 2 is inducible by a two-crossing election. If W denotes the maximum weight of an edge, then O(m2W) voters suffice.

Proof. For some number of candidates m, consider the following "Double-BubbleSort" construction of a two-crossing profile. There will be m(m - 1) + 1 voters; voter 1 ranks 1 ≻ 2 ≻ . . . ≻ m, which we more succinctly represent as the permutation 123 . . . m. Voter 2 ranks 213 . . . m, voter 3 ranks 231 . . .m, and so on, voter m ranks 23 . . .m1. In essence, one swap at a time, candidate 1 went from best to worst. For the following m- 1 voters, candidate 2 will go from best to second worst, one position at a time: 324 . . .m1, 342 . . .m1, . . . , 34 . . .m21. In the following rounds, we similarly bring from front to back candidates 3, 4, . . . m-1, each taking multiple swaps to reach their final position. Note that the swaps we do are precisely those done by a BubbleSort algorithm sorting in descending order. This construction is illustrated for m = 4 by the first 7 voters in Figure 2. To complete the profile, we need m(m- 1)/2 additional voters; consecutive voters will, once again, differ by a single adjacent swap. In particular, we go from m . . . 21 back to 12 . . . m by following the swaps of a BubbleSort algorithm sorting in ascending order, but iterating over the permutation in reverse order. Figure 2, voters v7 to v13, demonstrates this process. Note that the majority margins satisfy mc,c′ = 1 for c < c′ .

Why is this profile interesting? For any two candidates c ̸= c′ there are voters vi, vj with preference permutations τi = Acc′B and τj = Bcc′A; where X denotes the reverse of permutation X. This means that, if we add one additional copy of voters vi, vj to our profile, then all majority margins stay unchanged, except for mc,c′ and mc′ ,c, which increase/decrease by 2. Since c, c′ were arbitrary, this means that we can increase/decrease any majority margin by 2 without affecting the others, 3 by adding two additional voters. If weights are odd, this can be done repeatedly until our profile has margins agreeing to the weights in the tournament. Fixing the margin for a weight w ≤ W requires O(w) additions of voters, so overall we need at most O(m2W) voters. The case of even weights is similar: add an additional m . . . 21 voter to our original profile, and then proceed analogously.

The previous result shows that, essentially, the computational complexity of all known (weighted) tournament solutions is unchanged from the general case by restricting to twocrossing elections. Thus, we have the following.

Corollary 8. Determining the winners for Slater, Banks, Minimal Extending Set, Tournament Equilibrium Set, Kemeny and Ranked Pairs is NP-hard under two-crossing elections.

2 Nonexistent edges are considered to have weight 0.

3 Subject to the implicit constraint that mc,c′ +mc′,c = 0.

5 Young's Rule

In this section we show how Young scores can be computed in polynomial time by setting up integer programs whose LP relaxations have totally unimodular matrices. This means that vertices of the feasible regions have integer coordinates, so it is enough to solve the LPs.

Theorem 9. Given a two-crossing profile P with voter set V and candidate set C, and a candidate c ∈ C, the weak and strong Young scores of c can be computed in polynomial time.

Proof. We present the algorithm for the weak Young score, the strong case being analogous. We are hence interested in removing a minimal number of voters such that the majority margins satisfy mc,c′ ≥ 0 for all c′ ∈ C \ {c}. To do so, set up an integer program P with variables (xv)v∈V ∈ {0, 1}, where xv is 1 iff voter v is kept; i.e. it is not removed. Then, mc.c′ ≥ 0 can be rewritten as ∑v∈V xv Jc ≻v c′ K ≥ 0; where by JSK = 2[S] - 1 we mean 1 when S holds and -1 otherwise. The goal is to maximize ∑v∈V xv. If we ignore the xv ∈ {0, 1} constraints and henceforth assume that voters are ordered in a two-crossing fashion, then the constraints matrix of P satisfies a property similar to the row-wise version (implicit from now on) of C1P�: it consists of values ±1 and on each row ones form a circular interval. Unfortunately, not all such matrices are totally unimodular; e.g the 2 × 2 matrix with 1 on the main diagonal and -1 otherwise.

To mitigate this difficulty, we need a slightly different approach: we will successively check for each value s = n, n - 1, . . . , 0 whether a solution keeping exactly s of the n voters exists. For a fixed s, we add the additional constraint that ∑v∈V xv = s. With the sum of the x's fixed we can rewrite our main inequalities as follows:

Therefore, for a fixed s, our integer program Ps consists of checking the feasibility of the following constraints:

At this point, if we relax constraints (3) to 0 ≤ xv ≤ 1, then the matrix of the resulting linear program Ls satisfies C1P�. Unfortunately, this still does not guarantee total unimodularity; e.g. the 3 × 3 matrix with 0 on the main diagonal and 1 otherwise has determinant 2 /∈ {-1, 0, 1}.

In one last step, we slightly adjust our constraints to get a matrix which is C1P, and hence provably totally unimodular [Fulkerson and Gross, 1965]. Note that constraints (1) and (3) do not make use of circularity, so only constraints (2) might need adjustments. Consider some constraint ∑v∈V xv [c ≻v c′ ] ≥ ⌈ s2 ⌉ needing adjustment; this is because [c ≻v c′ ] is of the form 11 . . . 1100 . . . 0011 . . . 11 as v ranges over the voters. We can then write

For this equivalent condition, the coefficients [c′ ≻v c] are of the form 00 . . . 0011 . . . 1100 . . . 00 as v ranges over V . Therefore, if we replace each constraint which uses circularity as such, the matrix of the resulting LP will be C1P, and so totally unimodular. This means that the feasible region has integer vertices [Hoffman and Kruskal, 2016], so the IP and the LP are equifeasible. Note that the replacements we made in (2) proved total unimodularity, but need not be executed in practice; i.e. it is enough to check the feasibility of Ls. If we now use any polynomial time algorithm for checking feasibility, like [Karmarkar, 1984], the poly-time bound follows.

Theorem 10. Given a two-crossing profile P and c ∈ C, the strong/weak Young score of c can be computed in time O((n+m2 )n3/2 log n) by further developing our techniques.

6 The Chamberlin-Courant Rule

In this section we show that computing the least possible dissatisfaction and also a winning committee for the Chamberlin-Courant rule (CC in this section) can both be achieved in polynomial time under two-crossing elections. Since the recognition problem can be solved in polynomial time by Theorem 6, assume voters V = [n] are ordered such that our profile is two-crossing with respect to the identity permutation. For the following key lemma, we call a k-assignment function w illegal if there are two candidates a ̸= b and four voters i1 < i2 < i3 < i4 such that w(i1) = w(i3) = a and w(i2) = w(i4) = b. We call w legal if it is not illegal.

Lemma 11. For any instance (P, ρ, k) of CC there exists a legal k-assignment wopt that is optimal for ρ and P.

Proof. Start with any optimal k-assignment w. If w is legal, then we are done, otherwise let a ̸= b and i1 < i2 < i3 < i4 witnesses the illegality of w. Since P is two-crossing we know it can not be the case that [a ≻i1 b] = [a ≻i3 b] ̸= [b ≻i2 a] = [b ≻i4 a], as that would result in 3 crosses for the pair (a, b). Therefore, for at least one of i1, i2, i3, i4 assignment w assigns a candidate from {a, b} which is less preferred than the other, so just exchanging a for b, or viceversa, for that voter results in an assignment w′ such that

Φρ(P,w′ ) ≤ Φρ(P,w). Since w was optimal, it follows that w′ is also optimal. We can now replace w by w′ and repeat the reasoning iteratively, until we eventually reach a legal optimal k-assignment wopt. It remains to show that this process terminates, but this is easy to see since at each step we replace a voter's assigned candidate with one that is strictly more preferred by them.

To find a winning committee for CC it is enough to find an optimal k-assignment for ρ and P. Given Lemma 11, we can limit our search to legal k-assignments. It turns out that legal k-assignments admit a second characterisation, as follows. The proof is straightforward, so we leave it to the reader.

Proposition 12. A k-assignment w = w(1), w(2), . . . , w(n) is legal iff for any candidates a ̸= b there are no a's between the first and the last b or no b's between the first and last a.

Given this, any legal assignment w induces a strict partial order relation →∗ over C, where a →∗ b for a ̸= b iff there are b's between the first and the last a in w. Note that this implicitly requires no a's between the first and the last b, by Proposition 12. Observe that two candidates a ̸= b are incomparable with respect to →∗ iff all a's precede all b's in w, or vice-versa. Relation→∗ satisfies an additional property: if a ̸= b are incomparable, then there can be no c /∈ {a, b} such that a →∗ c and b →∗ c, since a structure of the form a . . . c . . . a . . . b . . . c . . . b occurring in w would be illegal for pairs (a, c) and (b, c). These being said, one can now observe that the covering relation → of →∗ ; i.e. the inclusion minimal relation with the same transitive closure; is a forest of directed trees. 4 Since our partial order →∗ is finite, there exists at least one maximal element crt ∈ C, which we call a "root" element; i.e. such that there is no c ∈ C with c →∗ crt . Let us now analyze w with respect to crt . Since crt is maximal, for all c ∈ C \{crt }, no crt 's occur between the first and the last c in w. In other words, if we consider the set w-1 (crt ) of positions where crt occurs in w, then all c's occur between two consecutive crt 's, or before/after the first/last crt . Put differently, candidate crt "splits" the range 1 . . . n into buckets delimited by consecutive entries in w-1 (crt ) ∪ {0, n + 1}, such that any candidate c ∈ C \ {crt } appears in at most one bucket. This reasoning can then be carried out recursively in each bucket as well.

The idea of our approach can now be stated intuitively: we will proceed by dynamic programming, solving the main problem by trying out all possible values of w-1 (crt), and then invoking recursively on each resulting bucket. There are a number of burning issues at this point: (i) there are exponentially many values of w-1 (crt ) to try, (ii) there are exponentially many ways to distribute the number k of representatives into the buckets (iii) how do we ensure that no candidate is used in two distinct buckets, maybe further down the recursion, fact which might render the assignment illegal? Before addressing (i)-(ii) specifically, let us first give a preliminary version of the dynamic program, which will run in exponential time, and argue for its correctness in addressing (iii). Introduce dp[ℓ, r, t] for 1 ≤ ℓ ≤ r ≤ n, 1 ≤ t ≤ k to mean the least total dissatisfaction attainable for voters in [ℓ : r] using a legal t-assignment restricted to those voters. For ease of presentation, we use the degenerate base-cases dp[ℓ, ℓ - 1, -] = 0 for ℓ ∈ [n + 1] and dp[ℓ, r, 0] = ∞ for 1 ≤ ℓ ≤ r ≤ n. Then, the recurrence relation is:

4 We do not use this fact explicitly, but it helps gain intuition for the DP which follows.

where we wrote w1, . . . , wx for the elements of w-1 (crt ) and used the convention that w0 = ℓ - 1 and wx+1 = r + 1. In other words: we choose the root candidate crt , we choose w-1 (crt), and we choose a way to distribute the remaining t-1 candidates among the buckets; each bucket is then solved "recursively" with the respective allowed committee size. For completeness, subproblems can be computed in increasing order of t, breaking ties arbitrarily. The cost of an optimal k-assignment wopt will be in dp[1, n, k] at the end. To retrieve one such wopt, additional bookkeeping is required: for each subproblem (ℓ, r, x) keep track of which values of crt , x, w1, . . . , wx and t0, . . . , tx were used to achieve the minimum, and then at the end trace those back to build wopt.

As argued previously, not only does this DP require exponential time to compute, it is not even clearly correct, reason being that it can produce illegal k-assignments by reusing candidates, especially along different branches of the recursion. However, note that this comes at a price: whenever a candidate is reused it is counted as a new candidate out of the maximum of k allowed. Nevertheless, none of this is harmful: consider the reconstructed optimal assignment wopt returned by the DP. This is a k-assignment since we only ever over-count candidates in the assembly, but never under-count. By construction, our recurrence clearly correctly considers all legal k-assignments, and will thus return a cost at most that of the least dissatisfaction legal k-assignment. Since by Lemma 11 no illegal k-assignment can be better than the best legal one, it follows that the returned assignment wopt is optimal, regardless of whether it is legal or not.

This proof approach can be summarized as follows, and is also implicit in the works of [Constantinescu and Elkind, 2021]: (1) show optimal solutions with a rigid structure exist; (2) set up a DP which looks only for solutions of this form; (3) note that the DP occasionally produces non-conforming solutions, but without affecting global correctness.

Having addressed concern (iii), we now need to speed up the DP - we need a faster way to compute (4). To achieve this, introduce an auxiliary second dynamic program, dp2[ℓ, r, t, crt ], with the same semantics as dp, but enforcing a certain value for the root crt . It is straightforward to see that

so it remains to show how dp2 can be computed in polynomial time, which we do with the following.

Lemma 13. dp2 satisfies the following recurrence relation: dp2[ℓ, r, t, crt ] = min {dp[ℓ, w1 - 1, t0] + ρ(w1, crt )+

Proof. The key stands in noting that it makes little sense to try out all values of w-1 (crt) = {w1, . . .} at once, so let us only go through all values of w1 ∈ [ℓ : r] and t0 ∈ [0 : t - 1] and observe the optimal substructure: for the left part, i.e. range [ℓ : w1-1], we use the optimal unrestricted solution with at most t0 candidates, i.e. dp[ℓ,w1 - 1, t0], for position w1 we take the fixed cost ρ(w1, crt ), while for the right part, i.e. range [w1 + 1, r], we have more choice. Namely, there are two possibilities: w1 was the only element in w-1 (crt ), in which case we need to take the best unrestricted solution with at most t-t0-1 candidates, the -1 accounting for candidate crt , i.e. dp[w1 +1, r, t-t0 -1], or |w-1 (crt )| > 1, in which case there is a w2 (and potentially more occurrences of crt ) to be placed; doing so optimally is precisely the definition of dp2[w1 + 1, r, t - t0, crt ]. 5 Altogether, we get (6).

We now outline our main result. Essentially, one can now compute subproblems in increasing order of r-ℓ, the optimal dissatisfaction being in dp[1, n, k] at the end.

Theorem 14. Given an instance (P, ρ, k) of CC where P is two-crossing, the optimal dissatisfaction and some winning committee can be computed in polynomial time.

We note that for "egalitarian" Chamberlin-Courant, where one is instead interested in minimizing the dissatisfaction of the most misrepresented voter, simply replacing '+' with max in the DPs preserves correctness.

7 Conclusions and FutureWork

We investigated two-crossing elections, giving an efficient recognition algorithm. Axiomatically, we showed that twocrossing elections are no different from general elections for any voting rule operating on the (weighted) majority tournament, such as Kemeny and Slater. Subsequently, we considered Young and the Chamberlin-Courant rule. In both cases we gave polynomial algorithms which are applicable in practice. We leave open whether faster solutions exist.

So far, two-crossing elections have not received the attention they deserve in the social choice literature. Algorithmically, we leave open whether Dodgson winners can be computed in polynomial time under two-crossing elections. kcrossing preferences for k > 2 are strictly more expressive than their two-crossing counterparts, but this comes with an increase in computational complexity; e.g. computing a winning committee for the Chamberlin-Courant rule, while being in P for two-crossing elections, becomes NP-hard under three-crossing elections. It would be interesting to establish such tight bounds for other voting rules; e.g. Young's; and, perhaps most importantly, to establish the hardness of recognizing k-crossing elections for k > 2. Axiomatically, it would be interesting to determine whether two-crossing elections admit a forbidden structure characterization, similarly to single-crossing elections [Bredereck et al., 2013].

5 No -1 here because crt is still actively "in use" at this point.

Acknowledgements

We thank Edith Elkind for the many useful discussions about two-crossing elections. We thank Costin Andrei Oncescu for mentioning a technique useful for improving the polynomial running time for Young's rule.