Structure in Dichotomous Preferences

1 Introduction

Preference aggregation is a fundamental problem in social choice, which has recently received a considerable amount of attention from the AI community. In particular, an important research question in computational social choice is the complexity of computing the output of various preference aggregation procedures. While for most common single-winner rules winner determination is easy, many attractive rules that output a committee (a fixed-size set of winners) or a ranking of the candidates are known to be computationally hard.

There are several ways to circumvent these hardness results, such as using approximate and parameterized algorithms. These standard algorithmic approaches are complemented by an active stream of research that analyzes the computational complexity of voting rules on restricted preference domains, such as the classic domains of singlepeaked [Black, 1958] or single-crossing [Mirrlees, 1971] preferences. This research direction was popularized by Walsh [2007] and Faliszewski et al. [2011], and has lead to a number of efficient algorithms for winner determination under prominent voting rules as well as for manipulation and control, which can be used when voters' preferences belong to one of these restricted domains [Walsh, 2007;

Martin Lackner

Vienna University of Technology, Austria lackner@dbai.tuwien.ac.at

Faliszewski et al., 2011; Brandt et al., 2010; Faliszewski et al., 2014; Betzler et al., 2013; Skowron et al., 2015b; Magiera and Faliszewski, 2014].

To the best of our knowledge, this line of work only considers settings where voters' preferences are given by total orders over the set of candidates; indeed, this is perhaps the most widely studied setting in the area of computational social choice. However, computationally complex preference aggregation problems may also arise when voters' preferences are dichotomous, i.e., each voter approves a subset of the candidates and disapproves the remaining candidates. Committee selection rules for voters with dichotomous preferences, or approval-based rules, have recently attracted some attention from the computational social choice community, and for two prominent such rules (specifically, Proportional Approval Voting (PAV) [Kilgour and Marshall, 2012] and Maximin Approval Voting (MAV) [Brams et al., 2007]) computing the winning committee is known to be NP-hard [Aziz et al., 2014; LeGrand et al., 2007]. It is therefore natural to ask if one could identify a suitable analogue of singlepeaked/single-crossing preferences for the the dichotomous setting, and design efficient algorithms for approval-based rules over such restricted dichotomous preference domains.

To address this challenge, in this paper we propose and explore a number of domain restrictions for dichotomous preferences that build on the same intuition as the concepts of single-peakedness and single-crossingness. Some of our restricted domains are defined by embedding voters or candidates into the real line, and requiring that the voters' preferences over the candidates "respect" this embedding; others are obtained by viewing dichotomous preferences as weak orders and requiring them to admit a refinement that has a desirable structural property. Surprisingly, these approaches lead to a large number of concepts that are pairwise nonequivalent and capture different aspects of our intuition about what it means for preferences to be "one-dimensional". We analyze the relationships among these restricted preference domains, (see Figure 3), and discuss the complexity of detecting whether a given dichotomous profile belongs to one of these domains. We then show that these domains are useful from the perspective of algorithm design, by providing polynomial-time and FPT algorithms for PAV and MAV under some of these domain restrictions. The full version of this paper is available on arXiv [Elkind and Lackner, 2015].

2 Basic Definitions

Let C = {c1, . . . , cm} be a finite set of candidates. A partial order ≻ over C is a reflexive, antisymmetric and transitive binary relation on C; a partial order ≻ is said to be total if for each c, d ∈ C we have c ≻ d or d ≻ c. We say that a partial order ≻ over C is a dichotomous weak order if C can be partitioned into two disjoint sets C + and C - (one of which may be empty) so that c ≻ d for each c ∈ C +, d ∈ C - and the candidates within C + and C - are incomparable under ≻.

An approval vote on C is an arbitrary subset of C. We say that an approval vote v is trivial if v = ∅ or v = C. A dichotomous profile P = (v1, . . . , vn) is a list of n approval votes; we will refer to vi as the vote of voter i. We write vi = C\vi. We associate an approval vote vi with the dichotomous weak order ≻vi that satisfies c ≻vi d if and only if c ∈ vi, d ∈ vi. Note that vi = ∅ and vi = C correspond to the same dichotomous weak order, namely the empty one.

A partial order ≻′ over C is a refinement of a partial order ≻ over C if for every c, d ∈ C it holds that c ≻ d implies c ≻′ d. A profile P ′ = (≻1, . . . ,≻n) of total orders is a refinement of a dichotomous profile P = (v1, . . . , vn) if ≻i is a refinement of ≻vi for each i = 1, . . . , n.

Let ◁ be a total order over C. A total order ≻ over C is said to be single-peaked with respect to ◁ if for any triple of candidates a, b, c ∈ C with a◁b◁c or c◁b◁a it holds that a ≻ b implies b ≻ c. A profile P of total orders over C is said to be single-peaked if there exists a total order ◁ over C such that all orders in P are single-peaked with respect to ◁.

A profile P = (≻1, . . . , ≻n) of total orders over C is said to be single-crossing with respect to the given order of votes if for every pair of candidates a, b ∈ C such that a ≻1 b all votes where a is preferred to b precede all votes where b is preferred to a; P is single-crossing if the votes in P can be permuted so that it becomes single-crossing with respect to the resulting order of votes.

A profile P = (≻1, . . . ,≻n) of total orders over C is said to be 1-Euclidean if there is a mapping ρ of voters and candidates into the real line such that c ≻i d if and only if |ρ(i) - ρ(c)| < |ρ(i) - ρ(d)|. A 1-Euclidean profile is both single-peaked and single-crossing.

3 Preference Restrictions

We will now define a number of constraints that a dichotomous profile may satisfy. Most of these constraints can be divided into two basic groups: those that are based on ordering voters and/or candidates on the line and requiring the votes to respect this order (this includes VEI, VI, CEI, CI, DE, and DUE), and those that are based on viewing votes as weak orders and asking if there is a single-peaked/single-crossing/1Euclidean profile of total orders that refines the given profile (this includes PSP, PSC, and PE); we remark that the study of the latter type of constraints was initiated by Lackner [2014]. We will also consider constraints that are based on partitioning voters/candidates (2PART and PART), as well as two constraints (WSC and SSC) that have been introduced in a recent paper of Elkind et al. [2015] in order to understand the best way of extending the single-crossing property to weak orders.

Fix a profile P = (v1, . . . , vn) over C.

1. 2-partition (2PART): We say that P satisfies 2PART if P contains only two distinct votes v, v′ , and v ∩ v′ = ∅, v ∪ v′ = C.
2. Partition (PART): We say that P satisfies PART if C can be partitioned into pairwise disjoint subsets C1, . . . , Cℓ such that {v1, . . . , vn} = {C1, . . . , Cℓ} (i.e., each voter in P approves one of the sets C1, . . . , Cℓ).
3. Voter Extremal Interval (VEI): We say that P satisfies VEI if the voters in P can be reordered so that for every candidate c the voters that approve c form a prefix or a suffix of the ordering. Equivalently, both the voters who approve c and the voters who disapprove c form an interval of that ordering. See Figure 1 for an example.
4. Voter Interval (VI): We say that P satisfies VI if the voters in P can be reordered so that for every candidate c the voters that approve c form an interval of that ordering. See Figure 2 for an example.
5. Candidate Extremal Interval (CEI): We say that P satisfies CEI if candidates in C can be ordered so that each of the sets vi forms a prefix or a suffix of that ordering. Equivalently, both vi and vi form an interval of that ordering.
6. Candidate Interval (CI): We say that P satisfies CI if candidates in C can be ordered so that each of the sets vi forms an interval of that ordering.
7. Dichotomous Uniformly Euclidean (DUE): We say that P satisfies DUE if there is a mapping ρ of voters and candidates into the real line and a radius r such that for every voter i it holds that vi = {c : |ρ(i) - ρ(c)| ≤ r}.
8. Dichotomous Euclidean (DE): We say that P satisfies DE if there is a mapping ρ of voters and candidates into the real line such that for every voter i there exists a radius ri with vi = {c : |ρ(i) - ρ(c)| ≤ ri}.
9. Possibly single-peaked (PSP): We say that P satisfies PSP if there is a single-peaked profile of total orders P ′ that is a refinement of P.
10. Possibly single-crossing (PSC): We say that P satisfies PSC if there is a single-crossing profile of total orders P ′ that is a refinement of P.
11. Possibly Euclidean (PE): We say that P satisfies PE if there is a 1-Euclidean profile of total orders P ′ that is a refinement of P.
12. Seemingly single-crossing (SSC): We say that P satisfies SSC if the voters in P can be reordered so that for each pair of candidates a, b ∈ C it holds that either all votes vi with a ∈ vi, b ̸∈ vi precede all votes vj with a ̸∈ vj, b ∈ vj or vice versa.
13. Weakly single-crossing (WSC): We say that P satisfies WSC if the voters in P can be reordered so that for each pair of candidates a, b ∈ C it holds that each of the vote sets V1 = {vi : a ∈ vi, b ̸∈ vi}, V2 = {vi : a ̸∈ vi, b ∈ vi}, V3 = {v ∈ P : v ̸∈ V1 ∪ V2} forms an interval of this ordering, with V3 appearing between V1 and V2.

3.1 Relations

The relationships among the properties defined above are depicted in Figure 3, where arrows indicate containment, i.e., more restrictive notions are at the top. All these containments are strict. We will now sketch proofs of some of the relationships indicated in this diagram; see [Elkind and Lackner, 2015] for the omitted proofs.

The four arrows at the top level of the diagram are immediate: any profile with at most two distinct votes where each candidate is approved in at least one of these votes satisfies VEI, CEI and WSC, and by definition 2PART is a special case of PART.

To understand the arrows in the next level, we first characterize the dichotomous profiles that are weakly singlecrossing.

Lemma 1. A dichotomous profile P satisfies WSC if and only if there exist three votes u, v, w such that

(1) for every vi ∈ P it holds that ≻vi ∈ {≻u,≻v,≻w}, and

(2) ≻v is equal to either ≻u∩w or ≻u∪w.

Proof sketch. It is easy to check that every profile satisfying (1)-(2) satisfies WSC. For the converse direction, assume without loss of generality that the ordering of the votes v1 ⊏ v2 ⊏ · · · ⊏ vn witnesses that P satisfies WSC. Let u = v1, w = vn, and set C1 = u ∩ w, C2 = u ∩ w, C3 = u ∩ w, C4 = u ∩ w. The WSC property implies that for every ℓ = 1, 2, 3, 4, every a, b ∈ Cℓ, and every vi ∈ P we have a ∈ vi if and only if b ∈ vi, i.e., candidates in each Cℓ occur as a block in all votes. Note that v1 = u = C1 ∪ C2, vn = w = C1 ∪ C3.

Suppose that C1,C4 ̸= ∅. Then C1 ⊆ vi, C4 ⊆ vi for all vi ∈ P. Thus, if P contains a vote vi ̸= u,w, it has to be the case that vi = C1 = u ∩ w or vi = C1 ∪ C2 ∪ C3 = u ∪ w; moreover, if both of these votes occur simultaneously and are distinct from each other and u, w (i.e., C2, C3 ̸= ∅), the WSC property is violated. When C1 or C4 is empty, the analysis is similar; note, however, that trivial votes (vi = C and vi = ∅) may alternate arbitrarily without violating the WSC property (this is why the lemma is stated in terms of weak orders rather than approval votes).

We can now show that under mild additional conditions (no trivial voters/candidates) WSC implies VEI and CEI.

Proposition 2. Let P be a dichotomous profile that either contains only two distinct votes or contains no vote vi with vi = ∅. If P satisfies WSC, then it satisfies VEI.

Proof. Assume without loss of generality that P satisfies WSC with respect to an ordering of voters v1 ⊑ · · · ⊑ vn, and let u = v1, w = vn. We will show that P satisfies VEI with respect to ⊏. If P only contains two distinct votes, this claim is immediate, so assume that ∅ ̸∈ P. Consider a vote v ∈ P that is distinct from u and w. Since ∅ ̸∈ P, by Lemma 1 there exist i, j with 1 < i < j < n such that vk = u for k < i, vk = v for k = i, . . . , j, vk = w for k > j, and v ∈ {u ∪ w, u ∩ w}. Suppose first that v = u ∩ w. Then candidates in u ∩ w are approved by all voters, candidates in u \ w are approved by the first i - 1 voters, candidates in w\u are approved by the last n-j voters, and the remaining candidates are not approved by anyone. On the other hand, if v = u∪w, then candidates in u∩w are approved by all voters, candidates in u \ w are approved by the first j voters, candidates in w \ u are approved by the last n - i + 1 voters, and the remaining candidates are not approved by anyone.

The condition that the profile must not contain ∅ is necessary: the profile ({a, b}, ∅, {b, c}) satisfies WSC, but not VEI.

Proposition 3. Let P be a dichotomous profile that either contains only two distinct votes or in which every candidate is approved in at least one vote and disapproved in at least one vote. If P satisfies WSC, then it satisfies CEI.

Proof. Suppose that P is WSC with respect to an ordering of voters ⊏; let u and w be, respectively, the first and the last vote in this ordering. If P contains a trivial vote, it contains at most two non-trivial votes, in which case the claim is obvious. Thus, assume that it contains no trivial votes. Then we have u ∩ w = ∅ (any candidate in u ∩ w would be approved by all voters) and u ∩ w = ∅ (any candidate in u ∩ w would be disapproved by all voters). It is now easy to see that ordering the candidates so that all candidates approved by u precede all candidates approved by w witnesses that P is CEI.

To see that conditions of Proposition 3 are necessary, consider the profile ({a, b}, {b, c}) over {a, b, c, d} and the profile ({a, b}, {b}, {b, c}) over {a, b, c}: both of these profiles satisfy WSC, but not CEI.

Next, we will relate CEI and VEI to DUE.

Proposition 4. If a dichotomous profile P satisfies CEI or VEI, then it satisfies DUE.

Proof. Suppose first that P satisfies CEI with respect to the ordering c1◁· · ·◁cm of candidates. Map the candidates into the real line by setting ρ(ci) = i, and let r = m. We can now place each voter i to the left or to the right of all candidates at an appropriate distance so that the set of candidates within distance r from him coincides with vi. For VEI the argument is similar: if P satisfies VEI with respect to the ordering v1 ⊑ · · · ⊑ vn of voters, we place voters on the real line according to ρ(i) = i, let r = n, and place each candidate to the left or to the right of all voters at an appropriate distance.

The proof that WSC implies DUE is also based on our characterization of WSC preferences.

Proposition 5. If a dichotomous profile P satisfiesWSC, then it satisfies DUE.

Proof. Clearly empty votes can be ignored when checking whether a profile satisfies DUE, so assume P contains to empty votes. Then it contains at most three distinct votes u, v, w with v = u ∩ w or v = u ∪ w. Set ρ(c) = 1 for c ∈ u \ w, ρ(c) = 2 for c ∈ u ∩ w, ρ(c) = 3 for c ∈ w \ u, ρ(c) = 10 for c ̸∈ u ∪ w. We set r = 1 if v = u ∩ w and r = 2 if v = u ∪ w, and position the voters accordingly.

The last arrow on this level is from PART to DUE: here, the containment is straightforward, as the candidates approved by each voter can be placed as a block on the axis, with the respective voter(s) placed in the center of this block. Also, it is immediate that DUE implies VI and CI. Perhaps more surprisingly, the classes CI, DE, PSP and PE coincide.

Proposition 6. Let P be a dichotomous profile. Then the following conditions are equivalent: (a) P satisfies PE (b) P satisfies PSP (c) P satisfies CI (d) P satisfies DE.

Proof sketch. Suppose P satisfies PE, and let P ′ be a refinement of P that, together with a mapping ρ, witnesses this. Then P ′ is single-peaked and therefore P satisfies PSP. If P satisfies PSP, as witnessed by a refinement P ′ and an axis ◁, then P satisfies CI with respect to ◁. If P satisfies CI with respect to an order ◁ of candidates, we can map the candidates into the real axis in the order suggested by ◁ so that the distance between every two adjacent candidates is 1. We can then choose an appropriate approval radius and position for each voter. Finally, if P satisfies DE, as witnessed by a mapping ρ, we can use this mapping to construct a refinement of P; by construction, this refinement is 1-Euclidean (we may have to modify ρ slightly to avoid ties).

An argument similar to the one used in the proof of Proposition 6 shows that every PE profile is PSC. Interestingly, the converse is not true.

Example 1. Consider the profile P = ({a, b}, {a, c}, {b, c}) over C = {a, b, c}. It satisfies PSC, as witnessed by the single-crossing refinement (a ≻ b ≻ c, c ≻ a ≻ b, c ≻ b ≻ a). However, in every refinement of P the first voter ranks c last, the second voter ranks b last, and the third voter ranks a last. Thus, no such refinement can be single-peaked, and, consequently, no such refinement can be 1-Euclidean.

The equivalence between PSC and SSC is not entirely obvious: while it is clear that a profile that violates SSC also violates PSC, to prove the converse one needs to use an argument similar to the proof of Theorem 4 in [Elkind et al., 2015]. We omit the proof of this result, as well as the proof of the following proposition, due to space constraints.

Proposition 7. If a dichotomous profile P satisfies VI, it also satisfies SSC.

For all other pairs of constraints, we have examples (omitted) showing that one does not imply the other.

3.2 Detection

To exploit the constraints defined in Section 3, we have developed algorithms that can decide whether a given profile belongs to one of the restricted domains defined by these constraints. Our results are summarized in Table 1.

Clearly, verifying whether a given profile satisfies 2PART or PART is straightforward. For most of the remaining problems, we can proceed by a reduction to the classic CONSECUTIVE 1S problem [Booth and Lueker, 1976]. This problem asks if the columns of a given 0-1 matrix can be permuted in such a way that in each row of the resulting matrix the 1s are consecutive, i.e., the 1s form an interval in each row; it admits a linear-time algorithm [Booth and Lueker, 1976].

Theorem 8. Detecting whether a dichotomous profile satisfies CEI, CI, VI or VEI is possible in O(m · n) time.

Proof. Let C = {c1, c2, . . . , cm} and P = (v1, v2, . . . , vn). We construct an instance of CONSECUTIVE 1S in slightly different ways, depending on the property we want to detect. In all cases, we obtain a "yes"-instance if and only if the given profile has the desired property.

Let us start with CI. For each vote, we create one row of the matrix: for each i ∈ [n] and j ∈ [m], the j-th entry of the i-th row is 1 if cj ∈ vi and 0 otherwise. In this way, we obtain an m× n matrix. Permuting the columns of this matrix so that 1s form an interval in each row is equivalent to permuting candidates so that the set of candidates approved by each voter forms an interval. For CEI, we combine the matrix for CI with its complement, i.e., we add a second row for each vote vi, so that the j-the entry of that row is 0 of cj ∈ vi and 1 otherwise. A column permutation of the resulting m× 2n matrix such that 1s form an interval in each row corresponds to permuting candidates so that for each voter both the set of her approved candidates and the set of her disapproved candidates form an interval; this is equivalent to the CEI property. For VI and VEI the argument is similar.

For WSC, Elkind et al. [2015] provide an algorithm that works for any weak orders (not just dichotomous ones). They leave the complexity of detecting PSC and SSC as an open problem, and we have not been able to resolve it for dichotomous weak orders. The problem of recognizing DUE preferences remains open as well, though it is plausible that a linear-programming based algorithms similar to those of [Doignon and Falmagne, 1994; Knoblauch, 2010; Elkind and Faliszewski, 2014] exist.

4 Algorithms for Committee Selection

In this section, we consider two classic approval-based committee selection rules-Proportional Approval Voting (PAV ) and Maximin Approval Voting (MAV)-and argue that we can design efficient algorithms for these rules when voters' preferences belong to some of the domains in our list (for some of the richer domains, we may need to place mild additional restrictions on voters' preferences).

We start by providing formal definitions of these rules.

Definition 1. Every non-increasing infinite sequence of nonnegative reals w = (w1,w2, . . . ) that satisfies w1 = 1 defines a committee selection rule w-PAV . This rule takes a set of candidates C, a dichotomous profile P = (v1, . . . , vn) and a target committee size k ≤ |C| as its input. For every size-k subset W of C, it computes its w-PAV score as ∑vi∈P uw(|W ∩ vi|), where uw(p) = ∑pj=1 wj, and outputs a size-k subset with the highest w-PAV score, breaking ties arbitrarily. The w-PAV rule with w = (1, 12 , 1 3 , . . . ) is usually referred to simply as the PAV rule, and we write u(p) = 1 + · · · + 1p .

In what follows we assume that the entries of w are rational and wi can be computed in time poly(i).

Definition 2. Given a set of candidates C, a dichotomous profile P = (v1, . . . , vn) and a target committee size k ≤ |C|, the MAV -score of a size-k subset W of C is computed as maxvi∈P(|W \ vi| + |vi \ W|). MAV outputs a size-k subset with the lowest MAV score, breaking ties arbitrarily.

The w-PAV rule is defined by Kilgour and Marshall [2012], see also [Kilgour, 2010]. Intuitively, under this rule each voter is assumed to derive a utility of 1 from having exactly one of his approved candidates in the winning set; his marginal utility from having more of his approved candidates in the winning set is non-increasing. The goal of the rule is to maximize the sum of players' utilities. In contrast, MAV [Brams et al., 2007] has an egalitarian objective: for each candidate committee, it computes the dissatisfaction of the least happy voter, and outputs a committee that minimizes the quantity.

Computing the winning committee under MAV and PAV is NP-hard, see, respectively, [LeGrand et al., 2007] and [Skowron et al., 2015a; Aziz et al., 2014]. The hardness result for PAV extends to w-PAV as long as w satisfies w1 > w2; moreover, it holds even if each voter approves of at most two candidates or if each candidate is approved by at most three voters.

We will now show that PAV admits an algorithm whose running time is polynomial in the number of voters and the number of candidates if the input profile satisfies CI or VI and, furthermore, each voter approves at most s candidates or each candidate is approved by at most d voters, where s and d are given constants. More specifically, we prove that PAV winner determination for CI and VI preferences is in FPT with respect to parameter s and in XP with respect to parameter d. For simplicity, we state our results for PAV ; however, all of them can be extended to w-PAV .

In what follows, we write [x : y] to denote the set {z ∈ Z : x ≤ z ≤ y}.

Theorem 9. Given a dichotomous profile P = (v1, . . . , vn) over a candidate set C = {c1, . . . , cm} and a target committee size k, if |vi| ≤ s for all vi ∈ P and P satisfies VI, then we can find a winning committee under PAV in time O(22s · k · n).

Proof. Assume that P satisfies VI with respect to the order of voters v1 ⊑ · · · ⊑ vn. For each triple (i,A, ℓ), where i ∈ [1 : n], A ⊆ vi, and ℓ ∈ [0 : k], let r(i, A, ℓ) be the maximum utility that the first i voters can obtain from a committee W such that W ∩ vi = A, |W| = ℓ, and W ⊆ v1 ∪ . . . ∪ vi.

We have r(1,A, |A|) = u(|A|) for every A ⊆ v1 and r(1,A, ℓ) = -∞ for every A ⊆ v1, ℓ ∈ [0 : k] \ {|A|}. To compute r(i + 1, A, ℓ) for i ∈ [1 : n - 1], A ⊆ vi+1 and ℓ ∈ [0 : k], we let p = |A \ vi| and set

Indeed, every committee W with |W| = ℓ, W ∩ vi+1 = A, W ⊆ v1 ∪ . . . ∪ vi+1 contains exactly ℓ - p candidates from v1 ∪ . . . ∪ vi and its intersection with vi is of the form D ∪ (A ∩ vi), where candidates in D are approved by vi, but not vi+1. We output maxA⊆vn r(n, A, k).

This dynamic program has n · 2s · (k + 1) states, and the value of each state is computed using O(2s ) arithmetic operations. Assuming that basic calculations take constant time, we obtain a total runtime of O(22s · k · n).

A similar dynamic programming algorithm can be used if voters' preferences satisfy CI. We omit its description due to space constraints.

Theorem 10. Given a dichotomous profile P = (v1, . . . , vn) over a candidate set C = {c1, . . . , cm} and a target committee size k, if |vi| ≤ s for all vi ∈ P and P satisfies CI, then we can find a winning committee under PAV in time O(2s · n · m).

Our next theorem also considers CI and VI preferences, and deals with the case where no candidate is approved by too many voters. Just as the algorithms in the proofs of Theorems 9 and 10, the algorithms for this case are based on dynamic programming; we omit them due to space constraints.

Theorem 11. Given a dichotomous profile P = (v1, . . . , vn) over a candidate set C = {c1, . . . , cm} and a target committee size k, if |{i | c ∈ vi}| ≤ d for all c ∈ C and P satisfies CI or VI, then we can find a winning committee under PAV in time poly(d, m, n, kd ).

The reader may wonder if constraints on s and d in Theorems 9, 10 and 11 are necessary. We conjecture that the answer is yes, i.e., winner determination under PAV remains hard under CI and VI preferences.

However, for "truncated" weight vectors w we can find w-PAV winners in polynomial time. As the (1, 0, . . . )- PAV rule is essentially the classic Chamberlin-Courant rule [Chamberlin and Courant, 1983] for dichotomous preferences, our next result can be seen as an extension of the results of [Betzler et al., 2013] and [Skowron et al., 2015b] for the Chamberlin-Courant rule and single-peaked and singlecrossing preferences: while we work on a less expressive domain (dichotomous preferences vs. total orders), we can handle a larger class of rules (all weight vectors with a constant number of non-zero entries rather than just (1, 0, . . . , )).

Theorem 12. Consider a weight vector w where wi = 0 for i > i0 for some constant i0. Then given a dichotomous profile P = (v1, . . . , vn) over a candidate set C = {c1, . . . , cm} and a target committee size k, if P satisfies VI or CI, we can find a winning committee under w-PAV in polynomial time.

Moreover, for the more restricted domains, such as VEI, CEI, WSC and PART we can design polynomial-time algorithms for both MAV and PAV , under no additional constraints on preferences (again, our results extend to w-PAV ).

Theorem 13. Given a dichotomous profile P = (v1, . . . , vn) over a candidate set C = {c1, . . . , cm} and a target committee size k, if P satisfies VEI, CEI, WSC or PART, we can find a winning committee under MAV and PAV in polynomial time.

Proof sketch. Consider first VEI. Assume without loss of generality that P satisfies VEI for voter order v1 ⊏ · · · ⊏ vn. Each candidate in C belongs to one of the following four groups: C1 = v1 ∩ vn, C2 = v1 \ vn, C3 = vn \ v1, and C4 = v1 ∩ vn; candidates in C1 are approved by all voters and candidates in C4 are not approved by any of the voters.

Suppose first that |C1 ∪C2 ∪C3| < k. Then there exists an optimal committee for both PAV and MAV that contains all candidates in C1 ∪ C2 ∪ C3 and exactly k - |C1 ∪ C2 ∪ C3| candidates from C4. Hence, we can now assume that this is not the case. Then there exist an optimal committee that contains no candidates from C4.

Now, if |C1| ≥ k, an optimal committee for both PAV and MAV consists of k candidates from C1, and if |C1| < k, there exists an optimal committee that contains all candidates in C1. It remains to decide how to allocate the remaining places among candidates in C2 and C3. To do so, we observe that there is a natural ordering over each of these sets: given a pair of candidates (c, c′ ) in C2 × C2 or C3 × C3, we write c ≤ c′ if {i : c ∈ vi} ⊆ {i : c′ ∈ vi}. Note that every two candidates in C2 are comparable with respect to ≤, and so are every two candidates in C3. It is now easy to see that there exists an optimal committee (for PAV or MAV ) that consists of candidates in C1, top p candidates in C2 with respect to ≤ and top r candidates in C3 with respect to ≤ for some nonnegative values of p, r with p + r + |C1| = k. Thus, by considering at most k2 possibilities for p and r, we can find an optimal committee.

The argument for CEI is similar to the one for VEI: we have to decide how many candidates to select from each end of the candidate ordering witnessing that P satisfies CEI. For WSC, we can use the characterization in Lemma 1; the problem then boils down to deciding how many candidates to select from each of the sets u\w, u∩w and w\u. For PART and PAV , we can show that an optimal committee can be found by a natural greedy algorithm that at each point selects the candidate with the largest "marginal contribution" to the total utility. For PART and MAV , we check, for each t = 0, . . . , n, whether there exists a committee whose MAV -score is at most t. This is the case if for each voter v ∈ P we can select at least (|v| + k - t)/2 candidates from v. Thus, if v1, . . . , vℓ are the distinct votes in P, we need to check that ∑ℓi=1 |vi| ≤ ℓt - (ℓ - 2)k.

5 Conclusions and Open Problems

We have initiated research on analogues of the notions of single-peakedness and single-crossingness for dichotomous preference domains. We have proposed many constraints that capture some aspects of what it means for dichotomous preferences to be single-dimensional, explored the relationship among them, and showed that these constraints can be useful for identifying efficiently solvable special cases of hard voting problems on dichotomous domains. The algorithmic results in Section 4 can be seen as a proof that our approach has merit; however, there is certainly room for improvement there, both in terms of removing restrictions on the sizes of approval sets and number of voters that approve each candidate (for PAV) and in terms of considering larger domains, such as PSC for PAV and CI/VI for MAV .

For many of our constraints, we have provided efficient algorithms for checking whether a given dichotomous profile satisfies that constraint; two notable open cases are DUE and PSC/SSC. In particular, it would be interesting to understand if every profile that satisfies both VI and CI also satisfies DUE; this can be seen as an analogue of the question of whether every single-peaked single-crossing profile of total orders is 1-Euclidean (see discussion in [Doignon and Falmagne, 1994; Elkind et al., 2014]). We can also ask if it is possible to detect if a given dichotomous profile is close to satisfying a structural constraint, and whether such "almoststructured" profiles have useful algorithmic properties; similar issues for profiles of total orders have recently received a lot of attention in the literature [Cornaz et al., 2012; 2013; Bredereck et al., 2013; Erd´elyi et al., 2013; Elkind and Lackner, 2014; Faliszewski et al., 2014].

Acknowledgments

The second author has been supported by the Austrian Science Foundation FWF, grant P25518-N23 and Y698.