---
title: "The Complexity of Election Problems with Group-Separable Preferences"
authors:
  - "Piotr Faliszewski"
  - "Alexander Karpov"
  - "Svetlana Obraztsova"
doi: "10.24963/ijcai.2020/29"
url: "https://ijcai.org/proceedings/2020/29"
pdf: "https://ijcai.org/proceedings/2020/0029.pdf"
venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"
year: 2020
pages: "203-209"
track: "Main track"
keywords:
  - "Agent-based and Multi-agent Systems: Voting"
  - "Agent-based and Multi-agent Systems: Algorithmic Game Theory"
  - "Agent-based and Multi-agent Systems: Computational Social Choice"
---

# The Complexity of Election Problems with Group-Separable Preferences

Piotr Faliszewski, Alexander Karpov, Svetlana Obraztsova

*Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 203-209. DOI: [10.24963/ijcai.2020/29](https://doi.org/10.24963/ijcai.2020/29)

## Abstract

We analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efficient algorithms if additionally the clone decomposition tree is of moderate height.

## Full text

## 1 Introduction

We study computational properties of elections for the case where voters' preferences are group-separable [Inada, 1964; 1969]. In this we follow a well-established line of research where the authors assume that the voters' preferences are nicely structured-e.g., are single-peaked [Black, 1958] or single-crossing [Mirrlees, 1971; Roberts, 1977]-and show that various NP-hard election-related problems either become polynomial-time solvable or, less frequently, remain computationally intractable (see, e.g., the survey of Elkind et al. [2016]). So far, group-separable preferences have received limited attention in the literature (especially regarding their computational properties, but see the work of Bredereck et al. [2016]) and we hope that our paper will convince more researchers of their value.

We consider the ordinal model of preferences, that is, we assume that each voter ranks the candidates from the most to the least appealing one. In the general, unrestricted case, each voter is free to report any such preference order, even if-intuitively-it would not correspond to any apparent evaluation of the candidates' merits. By assuming that the preference orders are structured in some way, we require that the voters follow some common, rational criteria. For example, Black [1958] introduced the notion of single-peaked preferences, where all the voters agree on some ordering of the candidates with respect to a given criterion (this ordering is referred to as the societal axis; in political elections it may, e.g., correspond to the standard left-to-right spectrum of opinions), each voter has his or her favorite position on the axis (i.e., each voter is free to choose any of the candidates as his or her most preferred one), and given two candidates that lay on the same side of the axis with respect to the voter's favorite candidate, the voter prefers the one closer to the favorite candidate. For example, if a voter ranks a centrist candidate on top, then he or she is forced to prefer a moderate left-wing candidate to an extreme left-wing one.

Figure 1: The feature hierarchy (clone decomposition tree) for the beverages example.

![Image](https://ijcai.org/proceedings/2020/fulltext/29/image_000000_2500f201b7aec7fbcb0081f14d1d8722b598cfebfdb56380fc1b56f0d637caee.png)

Group-separable preferences, introduced by Inada [1964; 1969], also capture a certain rationality assumption, but a completely different one. Formally, we say that the voters have group-separable preferences if each subset A of candidates, |A| ≥ 2, can be split into two parts, A′ and A′′ , such that each voter prefers all the members of one of these sets to all the members of the other. One interpretation of this is that there is a hierarchy of features that the candidates may have, up to some level of this hierarchy all the candidates from A have the same features, and for the level where they differ, some voters prefer the features of the candidates in A′ , whereas the others prefer the features of those in A′′ (the features do not need to be binary, but this is a natural case).

Example 1. To illustrate the above intuition, let us consider an example where the voters have preferences over five beverages: coffee, green tea, black tea, juice, and soda. There are three voters with the following preferences (we write a ≻ b to indicate that a voter ranks a above b):

v1 : coffee ≻ black tea ≻ green tea ≻ soda ≻ juice,

v2 : green tea ≻ black tea ≻ coffee ≻ juice ≻ soda,

v3 : soda ≻ juice ≻ black tea ≻ green tea ≻ coffee

To see that these preferences are group-separable, we make the following observations. First, if we consider the set of all the beverages, then each voter either prefers all the hot drinks to all the cold ones, or the other way round. Second, among the hot drinks, all the voters either prefer coffee to both kinds of tea or the other way round. In other words, all the voters agree that the beverages can be classified as in Figure 1 and form their preferences accordingly (such trees as in Figure 1

were already discussed by Inada [1964]). In particular, no voter would rank coffee above juice above green tea because it would put a cold drink between two hot ones.

We note that the tree presented in Figure 1 is, in fact, a clone decomposition tree for our preference profile [Elkind et al., 2012]; indeed, all the candidates in a given branch of the tree are clones in the sense that all the voters rank them consecutively. While not all decomposition trees correspond to group-separable preferences (see Section 2), for each election there is a polynomial-time computable canonical decomposition tree [Karpov, 2019; Elkind et al., 2012].

Assuming that the voters have single-peaked preferences (or single-crossing ones, or ones that are structured in some other appealing way) has various positive consequences. For example, if the number of voters is odd then there always exists a Condorcet winner (i.e., a candidate c that is preferred to every other candidate by a majority of voters). Further, many NP-hard election-related problems become polynomial-time solvable. While it is well-known that group-separable preferences behave equally nicely on the normative front (in particular, they also guarantee the existence of Condorcet winners), we show that their computational properties are more involved. To this end, we consider the problems of winner determination under the Chamberlin-Courant multiwinner voting rule [Chamberlin and Courant, 1983] and Young single-winner voting rule [Young, 1977], as well as two kinds of election control problems. We chose these problems because they all are NP-hard in the general setting, but become polynomial-time solvable if the voters' preferences are single-peaked (or single-crossing). On the high level, our main contribution is that:

Many (although not all) election-related NP-hard problems remain intractable even if the voters have group-separable preferences. Yet, often these problems can be solved more efficiently (often in polynomial time) if the clone decomposition tree for the given input preference profile has moderate height.

Briefly put, our NP-hardness results rely on the fact that if the clone decomposition tree has caterpillar structure (i.e., it is a path where each node on the path-except for the last onehas an edge to one additional node) then we have enough freedom in forming preference orders to adapt already existing NP-hardness proofs. For our positive results, we either use dynamic programming over the clone decomposition trees (storing an exponential amount of information with respect to the height of the tree) or show reductions to particularly structured integer linear programming (ILP) tasks. We omit some of the proofs due to restricted space.

## 2 Preliminaries

For an integer t, we write [t] to denote the set {1, . . . , t}. An election E = (C, V ) consists of a set of candidates C = {c1, . . . , cm} and a collection V = (v1, . . . , vn) of voters. Each voter vi is associated with preference order ≻vi , which ranks all the candidates from the most to the least desirable one. Given two disjoint subsets of candidates, A and B, we write vi : A ≻ B to indicate that vi prefers each member of A to each member of B. We extend this notation to three or more sets in a natural way, and for singleton sets we often omit braces. For example, given candidates a and b, by vi : a ≻ C \ {a, b} ≻ b we mean that voter vi prefers candidate a to all the other candidates, and prefers all the candidates to candidate b. We omit vi from this notation if it is clear from the context. For a voter vi and candidate c, we write posvi (c) to denote the position of c in vi's preference order (the top-ranked candidate has position 1, the next one has position 2, and so on).

(Weak) Condorcet winners. We say that a candidate c is a (weak) Condorcet winner if for every other candidate d a strict majority of the voters (at least half of the voters) ranks c above d. In general, a Condorcet winner may not exist, but if he or she exists, then he or she is unique. A Condorcet winner is also a weak Condorcet winner.

Single-winner voting rules. A single-winner voting rule is a function R that given an election E outputs a set of tied election winners (in practice, tie-breaking rules are needed, but we disregard this issue 1 ). A single-winner voting rule is (weak) Condorcet-consistent if it outputs exactly the Condorcet winner (the weak Condorcet winners) whenever he or she (they) exist. We focus on the following two rules:

1. Under the Plurality rule, each candidate gets score equal to the number of voters that rank him or her first, and the candidates with the highest score win.
2. Under the Young rule [Young, 1977], each candidate gets score equal to the smallest number of voters that need to be removed from the election for this candidate to become a weak Condorcet winner. The candidates with the lowest score win.

Naturally, the Young rule is (weak) Condorcet-consistent, whereas the Plurality rule is not.

Example 2. Consider the election from Example 1. The Plurality rule outputs three tied candidates, coffee, green tea, soda, whereas the Young rule outputs a unique winner, black tea (who is the Condorcet winner).

Multiwinner rules. Multiwinner voting rules are defined analogously to the single-winner ones, except that their input additionally includes the desired committee size k, and they output a family of committees-i.e., size-k subsets of candidates-that tie as election winners. We are interested in the Chamberlin-Courant (CC) multiwinner rule [Chamberlin and Courant, 1983], which is defined as follows: Let β be the Borda dissatisfaction function, defined for each positive integer i as β(i) = i - 1. Further, consider an election E = (C, V ), committee size k, and some committee W ⊆ C. The CC-dissatisfaction score of W is:

<!-- formula-not-decoded -->

Intuitively, each voter v contributes dissatisfaction β(i) to the committee, where i is the position of the committee member that v ranks highest; this candidate is referred to as the representative of v. The CC rule outputs the size-k committees with the lowest CC-dissatisfaction score. There are a number of variants of the CC rule which use other functions in place of β (or focus on the approval setting [Procaccia et al., 2008]), but for the sake of brevity we focus on the classic, Borda-based variant.

1 Occasionally, tie-breaking may affect the complexity of election problems [Obraztsova and Elkind, 2011; Obraztsova et al., 2011].

Example 3. In the election from Example 1, there are three CC winning committees of size k = 2. Each of them contains soda and one of the hot drinks. Their CC-dissatisfaction score is two (e.g., the committee {black tea, soda} receives one point from each of the first two voters and zero points from the last one).

Computational problems. We are interested in the following computational problems. In each of the problems below we are given an election E = (C, V ), a (preferred) candidate p (except for the CC-SCORE problem, where we are given committee size k instead), and a nonnegative integer t (except for the YOUNG-WINNER problem):

1. In the YOUNG-WINNER problem we ask if p is one of the Young winners of election E. In the YOUNG-SCORE problem we ask if p's Young score is at most t. Both problems are NP-hard [Brandt et al., 2015; Rothe et al., 2003] (indeed, the former problem is Θp2 -complete and the latter is NP-complete), but both are polynomialtime solvable for single-peaked [Brandt et al., 2015] and single-crossing [Magiera and Faliszewski, 2017] preferences.
2. In the CC-SCORE problem we ask if there is a size-k committee whose CC-dissatisfaction score is at most t. The problem is NP-complete [Procaccia et al., 2008; Lu and Boutilier, 2011] in general, but becomes polynomial-time solvable under both single-peaked [Betzler et al., 2013] and singlecrossing [Skowron et al., 2015b] preferences.
3. In the PLURALITY-CCAC problem 2 we are additionally given a set A of spoiler candidates (the voters' preferences include members of A), whereas in the CONDORCET-CCAV problem 3 we additionally get a collection W of spoiler voters. In the former problem we ask if there is a set A′ ⊆ A of at most t spoiler candidates such that p is a Plurality winner of election (C ∪ A′ , V ), whereas in the latter we ask if there is a collection W ′ of at most t spoiler voters such that p is the Condorcet winner of the election (C, V + W ′ ). Both problems were shown to be NP-complete by Bartholdi et al. [1992], whereas Faliszewski et al. [2011] and Brandt et al. [2015] showed polynomial-time algorithms for the single-peaked cases, and Magiera and Faliszewski [2017] did the same for single-crossing ones.

We also study the PLURALITY-CCDC and CONDORCETCCDV problems (constructive control by deleting candidates or voters, respectively). They are defined analogously to the CCAC/CCAV variants, but instead of adding spoiler candidates/voters, we ask if it is possible to make the preferred candidate a winner by deleting at most t candidates or voters, respectively. The difference between CONDORCET-CCDV and YOUNG SCORE is that in the former we ask about a Condorcet winner and in the latter about a weak one.

2 CCAC stands for constructive control by adding candidates.

3 CCAV stands for constructive control by adding voters.

## 3 Group-Separability and Clone Structures

The notion of group-separable preferences is due to Inada [1964; 1969]. We say that an election E is group separable (or, that the voters' preferences are group-separable) if each subset A ⊆ C of candidates, |A| ≥ 2, can be partitioned into two nonempty subsets, A′ and A′′ , such for each voter v ∈ V it holds that either v : A′ ≻ A′′ or v : A′′ ≻ A′ . It turns out that it is particularly convenient to look at groupseparable elections through the lenses of clone analysis.

We say that a subset B of candidates is a clone set in election E if all the voters rank the members of B consecutively. We write C(E) to denote the family of all clone sets of election E; we also refer to C(E) as the clone structure of E.

As discussed by Elkind et al. [2012], clone structures are hierarchical and are conveniently described using PQ-trees of Booth and Lueker [1976]: A PQ-tree over candidate set C is an ordered tree, where each leaf is labeled with a unique candidate and each internal node is either of type P or of type Q (for the sake of brevity, we will often treat candidates as if they were the leaves themselves). By reading the candidates associated with the leaves from left to right, we obtain a preference order referred to as the frontier of this tree. A preference order ≻ is consistent with a given PQ-tree if it can be obtained as its frontier by performing the following types of operations: (a) if a node is of type P, then its children can be permuted arbitrarily, and (b) if a node is of type Q, then the order of its children can be reversed.

If every preference order in an election E = (C, V ) is consistent with a given PQ-tree T (over the same candidate set), then we say that E is consistent with T . We say that T is a clone decomposition tree of E if E is consistent with T and for each set A of candidates, A is a clone set in E if and only if either (a) there is a subtree of T whose leaves are exactly the candidates fromA, or (b) there is a sequence of subtrees of T , whose leaves are consecutive children of the same Q-node, such that A is the union of the sets of leaves of these trees. Elkind et al. [2012] argued that for every election there is a clone decomposition tree and that it is, in essence, unique (up to permuting the order of children in nodes of type P and reversing the order of children of nodes of type Q). Further, this tree is easily computable in polynomial time. Karpov [2019] has shown that if an election is group-separable, then all the nodes in its clone decomposition tree are of type Q.

Example 4. Let E = (C, V ) be the election from Example 1. In addition to all the singleton sets and the set of all candidates, the clone structure of E consists of sets {juice, soda}, {black tea, green tea}, and {black tea, green tea, coffee}. All the preference orders in this election are consistent with the PQ-tree from Figure 1 (all nodes are of type Q, say). Indeed, this tree is a clone decomposition tree for E.

Let T be some PQ-tree over candidate set C. For a node T of T , we write C(T) to denote the set of candidates that appear as the leaves of the tree rooted at T. For example, for the tree from Figure 1 we have C(cold) = {juice, soda}.

## 4 Hardness Results and Caterpillar Trees

In this section we argue that nearly all our problems remain NP-hard even if the voters' preferences are group-separable (the YOUNG WINNER problem is the only exception-under group-separable preferences weak Condorcet winners always exist and it suffices to check if the given candidate p is one of them). We obtain all our NP-hardness proofs using the same trick, i.e., by noting that we can form a caterpillar PQ-tree (where all the nodes are type-Q) and ensure that all our preference orders are consistent with it. Caterpillar trees give us enough flexibility to either form simple NP-hardness proofs or adapt those already available in the literature.

A caterpillar tree consists of a core path and each node either lays on the path or is directly connected to a node on the path. In our case we will be interested in binary caterpillar PQ-trees (we let all nodes be of type Q). Let C = {c1, . . . , cm} be a set of candidates. We write CP(c1, . . . , cm) to mean the following caterpillar tree: There are internal nodes P1, . . . , Pm-1, where P1 is the root of the tree and for each i ∈ [m- 2], Pi has one leaf child ci and one internal-node child Pi+1. Further, Pm-1 has two leaf children, cm-1 and cm. 4

Observation 1. Consider a tree T = CP(c1, . . . , cm). Let A and B be two disjoint subsets of C such that C = A∪B (i.e., A and B form a partition of C). Then a preference order v of the form v : A ≻ B, where all the members of A are listed in the order of increasing indices and all the members of B are listed in the order of decreasing indices, is consistent with T .

Using Observation 1, we can show our first result (similar proofs work for CONDORCET-CCAV/CCDV).

Proposition 1. YOUNG-SCORE is NP-hard even for groupseparable elections.

Proof. We will give a reduction from the following classic variant of the X3C problem. The input instance I consists of a set X = {x1, . . . , x3k} and a family S = {S1, . . . , Sm} of size-3 subsets of X (each element of X belongs to exactly three sets in S). The question is if it is possible to choose k sets whose union is X. We assume that k ≥ 3. We form an instance of YOUNG-WINNER with candidate set C = {x1, . . . , x3k, p} and the following voters, whose preference orders are consistent with CP(x1, . . . , x3k, p) and, thus, are group-separable:

1. For each set Si ∈ S, there is a voter with preference order of the form X - Si ≻ p ≻ Si (in the language of Observation 1, we have A = X-Si and B = {p}∪Si).
2. We have m - k - 4 voters with preference order of the form p ≻ x3k ≻ · · · ≻ x1.

We ask if p's Young score is at most k, i.e., we ask if it is possible to ensure that p is a weak Condorcet winner by deleting at most k voters.

Prior to deleting any voters, for each candidate xi there are exactly (m - k - 4) + 3 = m - k - 1 voters who prefer p to xi and m- 3 voters who prefer xi to p. Since (m- 3) - (m- k - 1) = k - 2 &gt; 0, p is not a weak Condorcet winner.

4 Note that the core path in this tree is, e.g., P1, . . . , Pm-1, cm.

However, if there is a family of k sets from S whose union is X, then by deleting the corresponding voters we remove k-1 voters who prefer xi to p and one voter who prefers p to xi. Then we have (m-3-(k-1))-(m-k-1-1) = 0, so p and xi tie in their head-to-head contest. As this reasoning applies to all members of X, we have that p becomes a weak Condorcet winner. Thus, if I is a yes-instance then we also output a yes-instance.

For the other direction, we assume that it is possible to delete at most k voters so that p becomes a weak Condorcet winner. It does not make sense to delete voters who prefer p to all the other candidates, so we assume that we delete voters from the first group only. By a reasoning analogous to that in the previous paragraph, for each element xi we have to delete at least k - 1 voters who prefer xi to p and at most one who prefers p to xi. This is possible only if I is a yes-instance.

Corollary 1. CONDORCET-CCAV and CONDORCETCCDV are NP-hard even for group-separable elections.

For the case of CC-SCORE, we observe that its NPhardness proof of Skowron et al. [Skowron et al., 2015a, Theorem 3] has the following properties. The set C of candidates is partitioned into two subsets, A = {a1, . . . , an} and D = {d1, . . . , dm}, where D is a set of dummy candidates. Further, the set D is partitioned into groups D1,D2, . . . (where each Di contains consecutive members of D). Each voter has a preference order of the form ai ≻ aj ≻ Dx ≻ C \ (Dx ∪ {ai, aj}), where i &lt; j and x is some integer (and the orders of candidates within Dx and C \ (Dx ∪ {ai, aj}) are irrelevant). Such preference orders are consistent with caterpillar trees CP(a1, . . . , an, d1, . . . , dm) and, thus, the proof applies to group-separable preferences. We similarly adapt the NPhardness proofs for PLURALITY-CCAC/CCDC [Bartholdi et al., 1992; Hemaspaandra et al., 2007].

Corollary 2. CC-SCORE, PLURALITY-CCAC, and PLURALITY-CCDC are NP-hard even for group-separable elections.

Our NP-hardness proofs use caterpillar trees, which have the largest height possible. In the following sections we show algorithms for the case of trees with more moderate height.

## 5 Algorithm for the CCRule

In this section we focus on the CC-SCORE problem, which asks if there is a committee with at least a given CC score.

Theorem 1. There is an algorithm for CC-SCORE that given committee size k and an election E with m candidates and n voters, where the voters' preferences are group-separable and yield a clone decomposition tree of height h, runs in time O(2h ) · poly(n,m, k).

While, in general, our algorithm runs in exponential time, we note that if the clone decomposition tree has height h = O(logm) (which happens, e.g., if it is a balanced binary tree) then the algorithm runs in polynomial time. Our algorithm is based on dynamic programming over the clone decomposition tree of the input election; we describe it throughout the rest of this section. We first note that it suffices to focus on CC committees of a particular form.

Lemma 1. Let E = (C, V ) be a group-separable election and let T be its clone decomposition tree. Let S ⊆ C be some committee. There exists a committee S′ ⊆ C, |S′ | ≤ |S|, such that dissatcc E (S′ ) ≤ dissatcc E (S) and for each internal node T of T , whose children are T1, . . . , Tr (and appear in this order in the tree), exactly one of the following holds:

1. at most one of the sets C(T1), . . . ,C(Tr) has a nonempty intersection with S′ , or
2. exactly C(T1) and C(Tr) have nonempty intersections with S′ .

Proof. If committee S does not satisfy our condition then let T be some node of T where this condition is violated, and let T1, . . . , Tr be the children of T (in the order in which they appear in the tree). Let c1 be some arbitrary member of C(T1) and let cr be some arbitrary member of C(Tr). Since the condition is violated, it must be that S ∩ ⋃ri=1 C(Ti) contains at least two elements (because at least two sets among C(T1), . . . ,C(Tr) have nonempty intersection with S). We form S′′ = (S \ ⋃ri=1 C(Ti)) ∪ {c1, cr} and claim that S′′ satisfies our condition at node T, contains at most |S| candidates, and does not have higher dissatisfaction than S. Indeed, |S′′ | ≤ |S| and exactly C(T1) and C(Tr) have nonempty intersections with S′′ . To see why dissatcc E (S′′ ) ≤ dissatcc E (S), we note that for every voter v in E, his or her preference order either satisfies v : C(T1) ≻ C(T2) ≻ · · · ≻ C(Tr), or satisfies v : C(Tr) ≻ · · · ≻ C(T2) ≻ C(T1) (this follows because for group-separable preferences the clone decomposition trees contain Q-nodes only). In either case, if the highest-ranked member of S belonged to ⋃ri=1 C(Ti), then the highest ranked member of S′′ is either ranked at the same position or higher. Further, we see that for every node where S did not violate the conditions, committee S′′ also does not violate them. By repeating the above-described process for all the nodes where the lemma condition is violated we obtain the desired committee.

We will refer to the committees of the form described in Lemma 1 as normal. Our algorithm will compute a lowestdissatisfaction normal committee of up to a given size k, and then fill it in up to size k with arbitrary candidates. By Lemma 1, this will be a winning committee for our election. To this end, we will need a certain compact way of representing key properties of normal committees.

Let E = (C, V ) be some group-separable election and let T be its clone decomposition tree, whose root is node P0. Further, let S be a normal committee for E (and T ) and let P = (P0, ..., Pq) be a path leading from the root of T down to some node Pq (this node may either be an internal node or a leaf). We say that this path is relevant if C(Pq)∩S ̸= ∅ (i.e., if there is some member of S that is reachable from the root of T by a path that extends P). If P is relevant, then for each Pi, i ∈ [q], we define type(Pi) as follows (let Q1, . . . ,Qr be the children of node Pi-1):

1. type(Pi) = 1 if for each Qj, j ∈ [r], it holds that C(Qj) ∩ S ̸= ∅ if and only if Qj = Pi (in other words, Pi is the unique child of Pi-1 that has leaves in S);
2. type(Pi) = 2 if r≥ 2, C(Q1)∩S ̸= ∅, andC(Qr)∩S ̸= ∅ (i.e., exactly the two extreme children of Pi-1 have leaves in S; by definition, Pi is one of these children).

Since S is a normal committee, the above two types are the only ones possible. We define the type vector of the path P to be type(P) = (type(P1), . . . , type(Pq)). As we will next show, given P and type(P) it is possible to compute those voters in V whose representatives (with respect to S) are in C(Pq). We refer to this collection of voters as V (P, type(P)). (A crucial observation here is that this collection of voters does not depend on the actual contents of S, provided that they are consistent with type(P).)

Lemma 2. Let E = (C, V ) be an election and let T be its clone decomposition tree. Let S be some normal committee for E and let P = (P0, . . . , Pq) be some relevant path in T . There is an algorithm that given E, T , P , and type(P) computes V (P, type(P )).

Proof. Our algorithm proceeds by first setting V ′ to be the collection of all the voters (i.e., V ′ := V ) and then removing voters from V ′ until we are left with the desired collection. Specifically, we consider nodes P1, . . . , Pq in order and, while considering node Pi, we proceed as follows (let Q1, . . . ,Qr be the children of Pi-1):

1. If type(Pi) = 2 then we consider two cases. If Pi = Q1 then we remove from V ′ all the voters v for whom it holds that v : C(Qr) ≻ C(Q1); if Pi = Qr then we remove from V ′ all the voters v for whom it holds that v : C(Q1) ≻ C(Q1) (since T is a clone decomposition tree for a group-separable profile, we know that for each voter one of the above conditions holds).
2. If type(Pi) = 1 then we leave V ′ unchanged.

A simple induction shows that for each i ∈ [q], after considering node Pi, V ′ contains exactly those voters, whose representatives belong to C(Pi). Thus, in the end, V ′ = V (P, type(P)). It is also easy to verify that the algorithm runs in polynomial time.

We are now ready to present our main algorithm. The input consists of a group-separable election E = (C, V ) and committee size k. Additionally, we also compute E's clone decomposition tree T ; this can be done in polynomial time [Elkind et al., 2012]. The algorithm is based on dynamic programming. For each number k′ ∈ [k] of candidates, each path P = (P0, . . . , Pq) leading from the root of T to one of its internal nodes or leaves, and each vector T = (t1, . . . , tq) ∈ {1, 2}q-which specifies the intended type of P-we define function f(k′ , P, T) to be the lowest dissatisfaction achievable by a committee S ⊆ C(Pq), |S| ≤ k′ , among voters V (P, T). We note that for path Proot = (P0) and empty vector Troot = (), we have that f(k, Proot, Troot) gives exactly the dissatisfaction of a winning size-k committee for election E. It remains to show how to compute f efficiently.

Consider some integer k′ ∈ [k], a path P = (P0, . . . , Pq), and vector T = (t1, . . . , tq) ∈ {1, 2}q . If Pq is a leaf (and c is the candidate associated with this leaf), then f(k′ , P, Q) = dissatcc (C,V (P,T)) ({c}). This follows because, by definition of f, we can only consider committees that are nonempty subsets of {c}, so there is just one choice. If Pq is not a leaf, then let Q1, . . . ,Qr be its children within T . For j ∈ [r], we write P |Qj to denote (P0, . . . , Pq, Qj) and for t ∈ {1, 2} we write T|t to denote (t1, . . . , tq, t). We express f recursively as f (k′ , P, Q) = max(A, B), where:

<!-- formula-not-decoded -->

Intuitively, value A corresponds to choosing committee members from a tree rooted at a single child of Pq, whereas B corresponds to choosing some committee members from C(Q1) and some from C(Qr) (by Lemma 1 there is no need to consider other possibilities).

Using the above recursion and standard dynamic programming, it is possible to compute f(k, Proot, Troot) in time O(2h ) · poly(|C|, |V |, k), where h is the height of T . The O(2h ) factor comes from the fact that for each node of T we need to consider at most 2h possible types of paths that lead to it. As argued above, f(k, Proot, Troot) is the lowest dissatisfaction achievable by a committee of size (at most) k in our election and computing it suffices to decide CC-SCORE. Via dynamic programming tricks, we can also compute a committee that achieves this dissatisfaction.

## 6 Plurality Control

For the case of PLURALITY-CCAC and PLURALITY-CCDC we obtain a result analogous to that for CC-SCORE.

Theorem 2. There are algorithms for the PLURALITYCCAC and PLURALITY-CCDC problems that for groupseparable elections run in time O(4h ) · poly(n,m), where h is the height of the clone decomposition tree for the input election, n is the number of its voters, and m is the number of its candidates.

## 7 Young Rule and Condorcet Control

We will now present our algorithm for computing the Young score of a given candidate. Unfortunately the algorithm will not work in polynomial time even for elections with decomposition trees of height O(logm). Still, the running time will be subexponential, giving a strong argument that in this case the problem is not NP-hard.

Theorem 3. There is an algorithm that given an election E with m candidates and n voters, where the voters' preferences are group-separable and yield clone decomposition tree of height h, computes the Young score of a given candidate in time hO(h2 ) · poly(n,m).

Let E = (C, V ) be our input election and let p be the candidate in whose Young score we are interested. Let T be the clone decomposition tree for E, and let P = (P0, . . . , Ph) be the path leading from the root of T to a leaf node corresponding to p. Our algorithm forms an integer linear program (ILP) and then solves it using the algorithm of Eisenbrand and Weismantel [2018] (see also the overview of Gavenciak et al. [2018] for a discussion of modern ILP algorithms). For each voter v ∈ V , we have a binary variable xv which takes value 1 if the voter stays in the election (i.e., is not deleted), and which takes value 0 otherwise. To form constraints, we consider each node Pi, i ∈ [h - 1] ∪ {0}, separately, and for each we introduce two constraints. Let us fix some node Pi and let Q1, . . . ,Qr be its children, such that Qj = Pi+1. Let X be the collection of voters v such that v : C(Q1) ≻ · · · ≻ C(Qr) (we refer to them as Xvoters), and let Y be the set of voters for whom it holds that v : C(Qr) ≻ · · · ≻ C(Q1) (we refer to them as Y -voters; by the properties of group-separable preferences, we know that each voter is either of type X or of type Y ). We introduce the constraints as follows:

1. If j &gt; 1 then for p ∈ C(Pj) to be aweakCondorcet winner, there must be at least as many X-voters as Y -voters (or some member of C(Q1) would be strictly preferred to p). We form constraint ∑v∈X xv ≥ ∑v∈Y xv.
2. If j &lt; r then, by an analogous reasoning as above, we require that there are at least as many Y -voters as Xvoters and form constraint ∑v∈Y xv ≥ ∑v∈X xv.

One can verify that if all these constraints are satisfied, then p is a weak Condorcet winner. We set the goal in our ILP to be maximizing ∑v∈V xv (so that we delete as few voters as possible). The score of p is |V | - ∑v∈V xv.

For the running time, we have |V | variables and O(h) constraints. As all the coefficients in our constraints are either 1 or -1, the algorithm of Eisenbrand and Weismantel [2018] runs in time |V | · hO(h2 ) , which suffices for us. Analogous algorithms also work for Condorcet-CCAV/CCDV.

Corollary 3. There are algorithms that solve CONDORCETCCAV/CCDV for group-separable elections in time hO(h2 ) · poly(m, n), where h is the height of the clone decomposition tree for the input election, m is the number of candidates, and n is the number of voters.

## 8 Conclusions

So far, most algorithmic studies of restricted domains focused on positive results and provided efficient algorithms. This is the case for the single-peaked [Faliszewski et al., 2011; Conitzer, 2009] and single-crossing [Skowron et al., 2015b; Magiera and Faliszewski, 2017] domains, as well as for many of their variants [Peters and Elkind, 2016; Yu et al., 2013]. Indeed, there even are domains-such as SPOC [Peters and Lackner, 2017]-that lack good normative properties, but are useful algorithmically. We have shown that the groupseparable domain is somewhat different. It is known to have good normative properties, but to obtain efficient algorithms, one has to look deeper into its structure.

## Acknowledgements

This work was supported by the MOE (Singapore) under Tier-1 grant 2018-T1-001-118 and by the NTU SUG M4081985 grant. Alexander Karpov was Supported by the Basic Research Program of the National Research University Higher School of Economics.

## References

1. [Bartholdi et al., 1992] J. Bartholdi, III, C. Tovey, and M. Trick. How hard is it to control an election? Math- ematical and Computer Modeling, 16(8/9):27-40, 1992.
2. [Betzler et al., 2013] N. Betzler, A. Slinko, and J. Uhlmann. On the computation of fully proportional representation. Journal of Art. Int. Research, 47:475-519, 2013.
3. [Black, 1958] D. Black. The Theory of Committees and Elec- tions. Cambridge University Press, 1958.
4. [Booth and Lueker, 1976] K. Booth and G. Lueker. Test- ing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Com- puter and System Sciences, 13(3):335-379, 1976.
5. [Brandt et al., 2015] F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra. Bypassing combinatorial protec- tions: Polynomial-time algorithms for single-peaked elec- torates. Journal of Art. Int. Research, 53:439-496, 2015.
6. [Bredereck et al., 2016] R. Bredereck, J. Chen, and G. Woeginger. Are there any nicely structured preference profiles nearby? Math. Social Sciences, 79:61-73, 2016.
7. [Chamberlin and Courant, 1983] B. Chamberlin and P. Courant. Representative deliberations and representa- tive decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3):718-733, 1983.
8. [Conitzer, 2009] V. Conitzer. Eliciting single-peaked prefer- ences using comparison queries. Journal of Art. Int. Re- search, 35:161-191, 2009.
9. [Eisenbrand and Weismantel, 2018] F. Eisenbrand and R. Weismantel. Proximity results and faster algorithms for integer programming using the Steinitz lemma. In Proceedings of SODA-18, pages 808-816, 2018.
10. [Elkind et al., 2012] E. Elkind, P. Faliszewski, and A. Slinko. Clone structures in voters' preferences. In Proceedings of EC-12, pages 496-513, June 2012.
11. [Elkind et al., 2016] E. Elkind, M. Lackner, and D. Peters. Preference restrictions in computational social choice: Re- cent progress. In Proceedings of IJCAI-2016, pages 4062- 4065, 2016.
12. [Faliszewski et al., 2011] P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 209(2):89-107, 2011.
13. [Gavenciak et al., 2018] T. Gavenciak, D. Knop, and M. Koutecký. Integer programming in parameterized complexity: Three miniatures. In Proceedings of IPEC-18, pages 21:1-21:16, 2018.
14. [Hemaspaandra et al., 2007] E. Hemaspaandra, L. Hemas- paandra, and J. Rothe. Anyone but him: The complexity of precluding an alternative. Artificial Intelligence, 171(5- 6):255-285, 2007.
15. [Inada, 1964] K. Inada. A note on the simple majority deci- sion rule. Econometrica, 32(32):525-531, 1964.
16. [Inada, 1969] K. Inada. The simple majority decision rule. Econometrica, 37(3):490-506, 1969.
17. [Karpov, 2019] A. Karpov. On the number of group- separable preference profiles. Group Decision and Nego- tiation, 28(3):501-517, 2019.
18. [Lu and Boutilier, 2011] T. Lu and C. Boutilier. Budgeted social choice: From consensus to personalized decision making. In Proceedings of IJCAI-11, pages 280-286, 2011.
19. [Magiera and Faliszewski, 2017] K. Magiera and P. Fal- iszewski. How hard is control in single-crossing elections? Autonomous Agents and Multiagent Systems, 31(3):606- 627, 2017.
20. [Mirrlees, 1971] J. Mirrlees. An exploration in the theory of optimal income taxation. Review of Economic Studies, 38:175-208, 1971.
21. [Obraztsova and Elkind, 2011] S. Obraztsova and E. Elkind. On the complexity of voting manipulation under random- ized tie-breaking. In Proceedings of IJCAI-11, pages 319- 324, July 2011.
22. [Obraztsova et al., 2011] S. Obraztsova, E. Elkind, and N. Hazon. Ties matter: Complexity of voting manipula- tion revisited. In Proceedings of AAMAS-11, pages 71-78, May 2011.
23. [Peters and Elkind, 2016] D. Peters and E. Elkind. Prefer- ences single-peaked on nice trees. In Proceedings of AAAI- 16, pages 594-600, 2016.
24. [Peters and Lackner, 2017] D. Peters and M. Lackner. Pref- erences single-peaked on a circle. In Proceedings of AAAI- 2017, pages 649-655, 2017.
25. [Procaccia et al., 2008] A. Procaccia, J. Rosenschein, and A. Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3):353- 362, 2008.
26. [Roberts, 1977] K. Roberts. Voting over income tax sched- ules. Journal of Public Economics, 8(3):329-340, 1977.
27. [Rothe et al., 2003] J. Rothe, H. Spakowski, and J. Vogel. Exact complexity of the winner problem for Young elec- tions. Theory of Comp. Systems, 36(4):375-386, 2003.
28. [Skowron et al., 2015a] P. Skowron, P. Faliszewski, and A. Slinko. Achieving fully proportional representation: Approximability result. Artificial Intelligence, 222:67- 103, 2015.
29. [Skowron et al., 2015b] P. Skowron, L. Yu, P. Faliszewski, and E. Elkind. The complexity of fully proportional repre- sentation for single-crossing electorates. Theoretical Com- puter Science, 569:43-57, 2015.
30. [Young, 1977] H. Young. Extending Condorcet's rule. Jour- nal of Economic Theory, 16(2):335-353, 1977.
31. [Yu et al., 2013] Lan Yu, Hau Chan, and Edith Elkind. Mul- tiwinner elections under preferences that are single-peaked on a tree. In Proceedings of IJCAI-13, volume 13, pages 425-431, 2013.