# voting_in_twocrossing_elections__278bdc90.pdf

Voting in Two-Crossing Elections

Andrei Constantinescu and Roger Wattenhofer ETH Zürich {aconstantine, wattenhofer}@ethz.ch

We introduce two-crossing elections as a generalization of single-crossing elections, showing a number of new results. First, we show that twocrossing elections can be recognized in polynomial time, by reduction to the well-studied consecutive ones problem. Single-crossing elections exhibit a transitive majority relation, from which many important results follow. On the other hand, we show that the classical Debord-Mc Garvey theorem can still be proven two-crossing, implying that any weighted majority tournament is inducible by a two-crossing election. This shows that many voting rules are NP-hard under two-crossing elections, including Kemeny and Slater. This is in contrast to the single-crossing case and outlines an important complexity boundary between singleand two-crossing. Subsequently, we show that for twocrossing elections the Young scores of all candidates can be computed in polynomial time, by formulating a totally unimodular linear program. Finally, we consider the Chamberlin Courant rule with arbitrary disutilities and show that a winning committee can be computed in polynomial time, using an approach based on dynamic programming.

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 justiﬁable 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 com-

v1 v2 v3 v4 v5 v6 v7 1 2 3 3 3 3 1 2 1 2 4 4 1 3 3 3 1 2 1 4 4 4 4 4 1 2 2 2

Figure 1: Two-crossing proﬁle with 7 voters and 4 candidates. Each column, corresponding to a voter, lists alternatives in decreasing order of preference. Voters are given in a two-crossing order; i.e. any two of the four colored candidate trajectories cross at most twice.

mon 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 ﬁrst 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 ﬁeld. In most single-winner voting systems, ﬁnding 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 exis-

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

tence 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 proﬁle. 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 and Wattenhofer, 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 ﬁxed 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 proﬁle. 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 proﬁle 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 proﬁle 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 inﬁnite. 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 signiﬁcant 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 proﬁle 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 proﬁle P = ( v)v V , the total dissatisfaction of voters in V under a k-assignment w is given by Φρ(P, w) = P 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 dissatisﬁed 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 proﬁle 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

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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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].

k-Crossing Preferences. A proﬁle 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 ) C2 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 proﬁle 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 ) C2 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 proﬁle P, is there a permutation σ such that P is L with respect to σ? If yes, one is also interested in ﬁnding such a witnessing σ.

Lemma 1. For any permutation (σi)i V , proﬁle 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 ﬂipping ones and zeros on those columns with a one in the ﬁrst row of M. Then, any permutation of rows σ ﬁxing the ﬁrst row witnesses that M is C1P iff σ witnesses that M c is C1P.

Corollary 4. C1PREC and C1PREC are equivalent (interreducible with respect to complexity-preserving reductions). This also extends to ﬁnding witnessing permutations.

Recognizing C1P/C1P matrices and ﬁnding 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-C1PREC is NP-complete [Goldberg et al., 1995].

3 Recognizing k-Crossing Proﬁles

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 proﬁles for k > 1 has not been studied. We prove that recognizing two-crossing proﬁles reduces to recognizing C1P matrices, which is tractable in poly-time. Given a proﬁle 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 ) C2; 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 deﬁnition 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 proﬁle P, deciding whether it is two-crossing and, if afﬁrmative, ﬁnding a witnessing permutation can be done in time O(nm2).

We note that the construction for MP was ﬁrst 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 c P 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 ) C2 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 Weighted Majority 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 proﬁle 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?

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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

Theorem 7 (Debord-Mc Garvey for Two-Crossing Elections). Any weighted majority tournament with weights of the same parity2 is inducible by a two-crossing election. If W denotes the maximum weight of an edge, then O(m2W) voters sufﬁce.

Proof. For some number of candidates m, consider the following Double-Bubble Sort construction of a two-crossing proﬁle. 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 ﬁnal position. Note that the swaps we do are precisely those done by a Bubble Sort algorithm sorting in descending order. This construction is illustrated for m = 4 by the ﬁrst 7 voters in Figure 2. To complete the proﬁle, 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 Bubble Sort 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 proﬁle 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 proﬁle, 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 proﬁle 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 proﬁle, 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.

2Nonexistent edges are considered to have weight 0. 3Subject to the implicit constraint that mc,c + mc ,c = 0.

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 1 2 2 2 3 3 4 4 4 1 1 1 1 2 1 3 3 2 4 3 3 1 4 4 2 2 3 3 1 4 4 2 2 1 3 3 2 4 3 4 4 4 1 1 1 1 2 2 2 3 3 4

Figure 2: Construction in the proof of Theorem 7 for m = 4 candidates. Voters are arranged in a two-crossing order.

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 proﬁle 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 P 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 P 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 satisﬁes 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 difﬁculty, 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 ﬁxed s, we add the additional constraint that P v V xv = s. With the sum of the x s ﬁxed we can rewrite our main inequalities as follows: X

v V xv Jc v c K 0 iff X

v V xv (2 [c v c ] 1) 0 iff

v V xv [c v c ] X

v V xv iff X

v V xv [c v c ] ls

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

v V xv = s (1)

v V xv [c v c ] ls

m , c C \ {c} (2)

xv {0, 1}, v V (3)

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

At this point, if we relax constraints (3) to 0 xv 1, then the matrix of the resulting linear program Ls satisﬁes 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 P v V xv [c v c ] s

2 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 X

v V xv [c v c ] ls

v V xv (1 [c v c]) ls

v V xv [c v c] ls

v V xv [c v c] js

For this equivalent condition, the coefﬁcients [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 proﬁle 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 proﬁle 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 ﬁnd a winning committee for CC it is enough to ﬁnd 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 ﬁrst and the last b or no b s between the ﬁrst 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 ﬁrst and the last a in w. Note that this implicitly requires no a s between the ﬁrst 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 satisﬁes 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 ﬁnite, 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 ﬁrst 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 ﬁrst/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) speciﬁcally, let us ﬁrst 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

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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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:

dp[ℓ, r, t] = min

i=1 ρ(wi, crt) +

i=0 dp[wi + 1, wi+1 1, ti] :

crt C, 1 x r ℓ+ 1, ℓ w1 < . . . < wx r,

t0, . . . , tx 0 and t0 + . . . + tx = t 1 (4)

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

dp[ℓ, r, t] = min crt C dp2[ℓ, r, t, crt] (5)

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

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

min {dp[w1 + 1, r, t t0 1], dp2[w1 + 1, r, t t0, crt]} :

w1 [ℓ, r], 0 t0 t 1 (6) 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 ﬁxed 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 deﬁnition 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 Future Work We investigated two-crossing elections, giving an efﬁcient 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].

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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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.

[Bartholdi et al., 1989] J. Bartholdi, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difﬁcult to tell who won the election. Social Choice and Welfare, 6(2):157 165, 1989.

[Booth and Lueker, 1976] Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13(3):335 379, 1976.

[Brandt et al., 2015] Felix Brandt, Markus Brill, Edith Hemaspaandra, and Lane A. Hemaspaandra. Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. J. Artif. Int. Res., 53(1):439 496, may 2015.

[Brandt et al., 2016] Felix Brandt, Markus Brill, and Paul Harrenstein. Tournament solutions. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 3. Cambridge University Press, USA, 1st edition, 2016.

[Bredereck et al., 2013] Robert Bredereck, Jiehua Chen, and Gerhard J. Woeginger. A characterization of the single-crossing domain. Social Choice and Welfare, 41(4):989 998, 2013.

[Caragiannis et al., 2016] Ioannis Caragiannis, Edith Hemaspaandra, and Lane A. Hemaspaandra. Dodgson s rule and young s rule. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 5. Cambridge University Press, USA, 1st edition, 2016.

[Chamberlin and Courant, 1983] John Chamberlin and Paul Courant. Representative deliberations and representative decisions: proportional representation and the borda rule. American Political Science Review, 77(3):718 733, 1983.

[Chen et al., 2021] Chia-Hui Chen, Junichiro Ishida, and Wing Suen. Signaling under Double-Crossing Preferences. ISER Discussion Paper 1103rr, Institute of Social and Economic Research, Osaka University, Oct 2021.

[Constantinescu and Elkind, 2021] Andrei Costin Constantinescu and Edith Elkind. Proportional representation under singlecrossing preferences revisited. Proceedings of the AAAI Conference on Artiﬁcial Intelligence, 35(6):5286 5293, May 2021.

[Constantinescu and Wattenhofer, 2022] Andrei Costin Constantinescu and Roger Wattenhofer. Voting in two-crossing elections. ar Xiv preprint, ar Xiv:2205.00474, 2022.

[Elkind et al., 2012] Edith Elkind, Piotr Faliszewski, and Arkadii Slinko. Clone structures in voters preferences. Proceedings of the ACM Conference on Electronic Commerce, pages 496 513, 2012.

[Faliszewski et al., 2017] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Multiwinner voting: a new challenge for social choice theory. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 2, pages 27 47. AI Access, 2017.

[Fischer et al., 2016] Felix Fischer, Olivier Hudry, and Rolf Niedermeier. Weighted tournament solutions. In Felix Brandt, Vincent

Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 4. Cambridge University Press, USA, 1st edition, 2016. [Fitzsimmons and Hemaspaandra, 2020] Zack Fitzsimmons and Edith Hemaspaandra. Election score can be harder than winner. In ECAI 2020, 2020. [Fulkerson and Gross, 1965] Delbert Ray Fulkerson and Oliver Alfred Gross. Incidence matrices and interval graphs. Paciﬁc Journal of Mathematics, 15:835 855, 1965. [Goldberg et al., 1995] Paul Goldberg, Martin Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of dna. Journal of computational biology: a journal of computational molecular cell biology, 2:139 52, 03 1995. [Hemaspaandra et al., 1997] Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Exact analysis of dodgson elections: lewis carroll s 1876 voting system is complete for parallel access to np. J. ACM, 44(6):806 825, Nov 1997. [Hemaspaandra et al., 2005] Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel. The complexity of kemeny elections. Theoretical Computer Science, 349:382 391, 12 2005. [Hoffman and Kruskal, 2016] A. J. Hoffman and J. B. Kruskal. Integral boundary points of convex polyhedra. In Linear Inequalities and Related Systems. (AM-38), Volume 38, chapter 13, pages 223 246. Princeton University Press, 2016. [Karmarkar, 1984] Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC 84, pages 302 311, New York, NY, USA, 1984. Association for Computing Machinery. [Lu and Boutilier, 2011] Tyler Lu and Craig Boutilier. Budgeted social choice: from consensus to personalized decision making. In Proceedings of IJCAI 11, pages 280 286, 01 2011. [Mirrlees, 1971] James Mirrlees. An exploration in the theory of optimum income taxation. The Review of Economic Studies, 38(2):175 208, 1971. [Misra et al., 2017] Neeldhara Misra, Chinmay Sonar, and P. R. Vaidyanathan. On the complexity of chamberlin courant on almost structured proﬁles. In Jörg Rothe, editor, Algorithmic Decision Theory, pages 124 138, Cham, 2017. Springer International Publishing. [Peters and Lackner, 2020] Dominik Peters and Martin Lackner. Preferences single-peaked on a circle. Journal of Artiﬁcial Intelligence Research, 68:463 502, 06 2020. [Procaccia et al., 2008] Ariel Procaccia, Jeffrey Rosenschein, and Aviv Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30:353 362, 02 2008. [Roberts, 1977] Kevin Roberts. Voting over income tax schedules. Journal of Public Economics, 8(3):329 340, 1977. [Rothe et al., 2003] Jörg Rothe, Holger Spakowski, and Jörg Vogel. Exact complexity of the winner problem for young elections. Theory of Computing Systems, 36:375 386, 2003. [Skowron et al., 2015] Piotr Skowron, Lan Yu, Piotr Faliszewski, and Edith Elkind. The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 569:43 57, 2015. [Tucker, 1971] Alan C. Tucker. Matrix characterizations of circular-arc graphs. Paciﬁc Journal of Mathematics, 39:535 545, 1971.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)