Conditional and Sequential Approval Voting on Combinatorial Domains

1 Introduction

Collective decisions on combinatorial domains cover a large variety of common situations, such as finding a set of dates for a series of meetings, electing a committee of representatives, adopting or rejecting each of a series of yes-no questions about common facilities to be built, or finding a common set of movies for a group to watch together.

Several methods have been proposed and studied for making such collective decisions. An important source of problems is when voters have preferential dependencies between variables: someone may be willing to attend the second meeting on a Friday provided that the first meeting is not already on a Friday; someone may want Ann to be elected at the department council only if both Betty and Charles are not elected too (they all belong to the same research group and would have too much joint power); I may want to watch one comedy and one drama, but not two films of the same genre.

It has been argued many times that making decisions independently on each variable cannot take such preferential dependencies into account. If we want to deal with them, we have to allow voters to express these dependencies. Several classes of methods have been proposed and studied (see [Lang and Xia, 2016] for a recent survey). Direct methods work by asking voters a one-shot report of their preferences, expressed in some language that allows preferential dependencies to be (at least partly) specified; sequential methods proceed by eliciting the voters' preferences on a first (fixed)

variable, decide its value, broadcast it, then eliciting the voters' preferences on a second variable conditionally on the value chosen for the first one, and so on.

Most of the existing methods for voting in combinatorial domains assume that voters express, implicitly or explicitly, rankings over the values of variables, or else cardinal utility functions. Both may induce a cognitive burden to the voters, as well as an increased complexity in communication and computation. On the other hand, in simple domains, approval voting is a well-studied method for elections, where each voter may approve of any number of candidates, and the candidate with the largest number of approvals wins. Approval voting has nice properties, and is easy to use and understand [Brams and Fishburn, 2005].

Approval voting can be extended to combinatorial domains, and especially to committee elections. The simplest way, if we want to select k candidates, consists in selecting those with the largest k approvals. Other ways of extending approval voting to multiple winner elections have been considered and are surveyed in [Kilgour, 2010]. Similar methods can be used for multiple referenda, as argued in [Amanatidis et al., 2015], due to the structural similarity of committee elections and multiple referenda: in both cases, a decision has to be made over a set of possible subsets (of candidates in one case, of binary issues in the other case) subject to feasibility constraints (such as the number of winners in committee elections, or budget constraints in multiple referenda). However, the methods we know of for multiwinner approval voting do not allow voters to express conditional preferences; they must vote as if they had separable preferences.

We propose a family of methods for reconciliating the simplicity of approval voting with the possibility for voters to express preferential dependencies. In Section 3 we define conditional approval ballots where voters approve some values of variables conditionally on the value of some other variables. In Section 4 we define two first rules based on conditional approval ballots, where the winning alternative minimizes respectively the maximum or the sum, over all voters, of the number of 'disagreements', and we show that these rules generalize simple (or 'minisum') approval voting and minimax approval voting [Brams et al., 2007]. In Section 5 we define sequential conditional approval voting: given a fixed order of variables, the voters approve some of their values, one variable after the other. We conclude in Section 6.

2 Background and related work

In a committee (or multi-winner) election, there is a set of candidates C, a set of voters N, each casting a vote (or a ballot), and a number k of winners (or sometimes a more flexible constraint, or even no constraint at all such as in Hallof-Fame elections). In multiwinner approval ballotting, each voter casts an approval ballot where she approves as many candidates as she wants (in some variants, there are also constraints on the number of approvals on a ballot).

In simple multiwinner approval voting, the winners are simply the k candidates approved most often. Simple approval voting can be criticized for failing to guarantee a sufficient level of fairness or representativeness, and a number of other rules that map a collection of approval ballots to a set of winners have been studied; see [Kilgour, 2010] for a survey. One prominent such rule is minimax approval voting, where the elected committee minimizes the maximum, over all voters, of the number of 'disagreements' (i.e., formally, the Hamming distance) between the voter's ballot and the chosen committee [Brams et al., 2007]. Unlike simple approval voting, minimax approval voting is NP-hard [Moti and Ami, 1997] and manipulable, but it can be efficiently approximated [LeGrand et al., 2007; Caragiannis et al., 2010; Byrka and Sornat, 2014]; see [Misra et al., 2015] for its parameterized complexity. [Amanatidis et al., 2015] generalize these two rules to other aggregation functions, and [Baumeister et al., 2015] extend them beyond approval ballots.

Other multiwinner approval voting rules, such as proportional or satisfaction approval voting [Brams and Kilgour, 2014], have been recently studied from the point of view of computation [Aziz et al., 2015b] or of their properties [Aziz et al., 2015a]. A number of works address the computation of full proportional representation with approval ballots, two good representatives being [Procaccia et al., 2008] and [Skowron and Faliszewski, 2015]. The computational aspects of strategic behaviour for single- and multi-winner approval voting are adressed in [Meir et al., 2008] and in [Baumeister et al., 2010]. The properties of multiwinner voting rules are studied more generally in [Elkind et al., 2014].

Combinatorial domains are sets of alternatives consisting of the Cartesian product (or sometimes, a subset of it) of finite domain values corresponding to issues, variables, attributes, seats, or even individuals (in the case of committee elections). The main difficulty in voting in combinatorial domains is the presence of preferential dependencies. To deal with them, some approaches make use of compact representations, such as [Rossi et al., 2004; Conitzer et al., 2011; Li et al., 2011]. Some others make use of sequential voting, variable after variable, such as [Lang and Xia, 2009; dalla Pozza et al., 2011; Airiau et al., 2011]. None of them makes use of approval ballots. See [Lang and Xia, 2016] for a recent overview of voting in combinatorial domains.

3 Conditional approval ballots

Let X = ¶X1↪ ▷ ▷ ▷ ↪Xp♦ be a set of variables, each of them associated with a finite value domain Di. Let D = D1 ⇥ ▷ ▷ ▷ ⇥Dp, and D⇤ ✓ D be a set of feasible alternatives (by default, D⇤ = D). A group of voters have to decide of a common outcome in D⇤ . When Xi is binary, we will usually take Di = ¶xi↪ xi♦. For J ✓ ¶1↪ ▷ ▷ ▷ ↪ p♦ we note DJ = ⇥j2JDj, and for d = (d1↪ ▷ ▷ ▷ ↪ dp) 2 D, dJ denotes the tuple d projected to the indices in J.

For instance, in a designated-post committee election [Benoˆıt and Kornhauser, 2010], X is a set of different seats to be filled and their domains are the respective sets of candidates for each position (an alternative is feasible only if it does not assign the same candidate to more than one seat). In a standard committee election where the size of the committee is fixed to k, X can be identified with the set of candidates, with binary domains ¶elected, not elected♦, and an alternative is feasible iff k variables have value 'elected'. In a multiple referendum [Brams et al., 1998], X is a set of binary issues.

The most common way of using approval ballotting in such domains consists in asking voters to approve values for each variable separately. This does not require much communication, but it is not possible for voters to report conditional preferences. For instance, a voter may approve ¶m↪ f♦ ✓ D1 and ¶r↪ w♦ ✓ D2 but cannot express that he approves the red wine only if the main dish collectively chosen is meat.

As a running example, a group of friends have to decide on a common menu. The variables are X1 (main dish), with D1 = ¶m↪ f↪ v♦ (meat, fish, vegetarian dish), and X2 (drink), with D2 = ¶r↪ w↪ b♦ (red wine, white wine, beer).

One could also think of asking voters to specify all combinations of values they approve (possibly in a compact way by means of a propositional formula). Here, preferential dependencies can be expressed, but the communication is costly, and moreover, a problem is that once a voter obtains a value he does not like for a variable, his opinion about the other variables does not count. Assume for instance that a voter hates fish and beer, and wants red wine with meat. It is reasonable to expect that he approves the set of menus ¶mr↪ vw↪ vr♦, and disapproves mw↪mb↪ fr↪ fw↪ fb↪ vb. However, if the collective decision turns out to give the value fish to X1, our voter won't have a chance to express that he still does not want to drink beer.

A trade-off between these two (extreme) methods consists in allowing voters to approve sets of values for each variable, conditioned on the value of some other variables.

Definition 1. A conditional approval (CA) ballot over variables X1↪ ▷ ▷ ▷ ↪Xp with domains D1↪ ▷ ▷ ▷ ↪Dp is a pair

where G is a directed graph over ¶X1↪ ▷ ▷ ▷ ↪Xp♦, and for each i, Ai is a set of conditional approval statements ¶u : ai(u)♣u 2 DParG(Xi)♦, where ai(u) ✓ Di, and ParG(Xi) is the set of parents of Xi in G. B#Xi♣u = ai(u) denotes the projection of B over Xi conditioned by u.

We say that B is acyclic if G is acyclic. B is a separable CA ballot if G has no edges.

Most often, we will alleviate the notation and only write the CA statements (and not the graph) when we specify a CA ballot. Also, we omit some curly brackets when it cannot lead to any confusion (in particular, for singletons).

Definition 2. Given an CA ballot B and an assignment d = (d1↪ ▷ ▷ ▷ ↪ dp) 2 D1 ⇥ ▷ ▷ ▷ ⇥ Dp, we say that d disagrees with B on variable Xi if di ◁2 B#Xi♣dU , where U = ParG(Xi). The disagreement of d with respect to B, denoted by δ(d↪ B), is the number of variables Xi on which d disagrees with B.

Example 1. Consider a voter expressing the CA ballot

This voter has a preference for not having meat: B#X1 = ¶f↪ v♦; but in case the collective decision is to have meat, she still has her word to say about the drink, and approves (only) the red wine: B#X2 ♣ m = ¶r♦. If the collective decision is the vegetarian dish, then she approves both the red and the white wine: B#X2 ♣ v = ¶r↪ w♦. Now, d = mr disagrees with B on X1 but not X2, therefore δ(d↪ B) = 1 (she is not satisfied with the choice of the dish, but is satisfied by the choice of the drink given that the dish is meat). Likewise, we have δ(fw↪ B) = δ(vr↪ B) = δ(vw↪ B) = 0 (she is satisfied by the choice of the dish and the choice of the drink conditional on the value of the dish), δ(fr↪B) = δ(fb↪B) = δ(vb↪B) = 1, and δ(mw↪ B) = δ(mb↪ B) = 2.

Equivalently, p - δ(·↪B) can be seen as a utility function which counts the number of conditional preferences satisfied. Thus, even though voters are using approval-like ballots, the preferences they express are not dichotomous.

Observation 1. If B is acyclic and ai(u) 6= ; for all i  p and u 2 DParG(Xi), then δ(d↪ B) = 0 for some d 2 D.

This, however, is no longer true if B is not acyclic: let for instance B = ¶x1 : x2↪ x1 : x2↪ x2 : x1↪ x2 : x1♦, then for every d 2 D we have δ(d↪ B) = 1.

Conditional approval ballots have a clear resemblance with CP-nets [Boutilier et al., 2004]. For the sake of simplicity, assume that variables are binary and let N(B) the CP-net obtained by replacing all conditional approval sets u : ai(u) by u : ai(u) ≻ ai(u), with xi = xi. The semantics of B and N(B) are different: if ≻N(B) is the partial order over D induced from N(B), and ≻B the order defined by d ≻B d0 if δ(d↪ B) < δ(d0 ↪ B), then ≻B and ≻N(B) are incomparable:

Observation 2. There exists B and d↪ d0 such that d ≻B d0 and d0 ≻N(B) d.

This can be seen on this example: X = ¶X1↪X2↪X3♦; B = ¶x1, x1 : x2, x1 : x2, x1x2 : x3, x1x2 : x3, x1x2 : x3, x1x2 : x3♦. We have x1x2x3 ≻N(B) x1x2x3, because N(B) contains x1 ≻ x1, however x1x2x3 ≺B x1x2x3, because δ(x1x2x3↪ B) = 1 < δ(x1x2x3↪ B) = 2.

Note that δ(·↪B) is a function fromD to [0↪ p], but not all functions from D to [0↪ p] can be expressed by a CA ballot; this can be seen by a simple counting argument. Therefore, assuming that a voter's preferences are representable by a CA ballot is a domain restriction.

4 Conditional minisum and minimax

Definition 3. An n-voter conditional approval profile is a collection P = hB1↪ ▷ ▷ ▷ ↪Bni of CA ballots. It is separable if every Bi is a separable CA ballot. A CA irresolute rule is a function mapping any CA profile to a nonempty subset of D⇤ .

Resolute rules can be obtained by combining an irresolute rule with a tie-breaking mechanism: if F is an irresolute rule and T is a tie-breaking mechanism induced by a fixed priority ranking over D⇤ , then F T is the composition of F by T. (Note that T is a relation over an exponentially large set, and thus should be represented in some compact way; this has no impact in our results.) We now define two specific rules.

4.1 Conditional minisum

Definition 4. Given a CA profile P = hB1↪ ▷ ▷ ▷ ↪Bni, the conditional minisum rule outputs the outcomes that minimize the total number of disagreements over all voters:

v : ¶r↪w♦ v : b v : ¶r↪ b♦ v : ¶r↪w♦ v : ¶r↪w↪ b♦

and we have CondMiniSum(P ) = ¶mr↪ vr♦.

If P is separable, then the outcome of CondMiniSum(P ) can be obtained simply by decomposing the vote into a series of standard approval votes, variable by variable. Let C be a set of candidates; a (standard) approval profile is a collection of approval ballots (A1↪ ▷ ▷ ▷ ↪An) where Ai ✓ C for each i; the (standard) approval rule App maps any approval profile to a winner (or a set of tied winners), and is defined by App(A1↪ ▷ ▷ ▷ ↪ An) = argmaxc2C♣¶i : c 2 Ai♦♣.

Observation 3. If P = hB1↪ ▷ ▷ ▷ ↪Bni be a separable CA profile. Then CondMiniSum(P) = App(P #X1 ) ⇥ ▷ ▷ ▷ ⇥ App(P #Xp ), where P #Xi = (B#Xi 1 ↪ ▷ ▷ ▷ ↪B#Xi n ).

In particular, if all variables are binary, we are in the context of a multiple referendum without preferential dependencies between issues, and where the decision is made issue by issue according to majority.

On the other hand, classical committee elections correspond to a collection of such separable conditional approval ballots, where binary variables correspond to candidates, together with a constraint on the cardinality of the committee.

Observation 4. Let D = ¶yes↪ no♦p (plus possibly a cardinality constraint), and P = hB1↪ ▷ ▷ ▷ ↪ Bni a separable CA profile. Then CondMiniSum(P) coincides with the output of simple multiwinner approval voting (also called minisum in [Brams et al., 2007]).

4.2 Conditional minimax

Conditional minisum has a utilitarianistic flavor: minimizing the sum of disagreements corresponds to maximizing social welfare. We may instead take an egalitarian point of view and minimize the maximum disagreement:

Definition 5. Given a CA profile P = hB1↪ ▷ ▷ ▷ ↪Bni, the conditional minimax rule outputs the outcomes that minimize the maximum number of disagreements over all voters :

Example 2, continued. The only outcome that has a disagreement at most 1 (in fact, exactly 1) with every conditional ballot is fb, therefore CondMiniMax(P) = ¶fb♦: every agent is either happy with the fish, or unhappy with the fish, but in that case, happy with the beer given that the dish is fish.

A similar result as Observation 4 holds for conditional minimax:

Observation 5. Under the same assumptions as in Observation 4, CondMiniMax(P) is the output of minimax approval voting [Brams et al., 2007]).

4.3 Computation

Computing a winning committee for minimax approval voting is NP-hard [Moti and Ami, 1997], which of course carries over to conditional minimax approval voting. On the other hand, the polynomial time computation of winning committees for simple approval voting does not carry over to conditional minisum (even without feasibility constraints):

Proposition 1. Given a CA profile P and an integer k, deciding whether there exists d 2 D such that Pi δ(d↪ Bi)  k is NP-complete, even for binary variables and, for each voter, an acyclic dependency graph with maximal indegree 1.

Proof. The problem is clearly in NP. The hardness proof is based on a reduction from MAX2SAT. Consider an instance I of MAX2SAT, defined by a set of variables V = ¶x1↪ ▷ ▷ ▷ ↪ xp♦, a set of 2-clauses C = ¶C1↪ ▷ ▷ ▷ ↪Cn♦, and an integer t. We create a set of binary variables X = ¶X1↪ ▷ ▷ ▷ ↪Xp♦ and, for each clause Ci = lj _ lk, where lj 2 ¶xj↪ xj♦ and lk 2 ¶xk↪ xk♦, and j < k, a voter i whose CA ballot Bi is defined as follows (with the convention lj = xj when lj = xj):

• ÷ the dependency graph has a single edge Xj -!Xk.
• ÷ the CA statements are ¶xj↪ xj♦, lj : ¶xk↪ xk♦, lj : ¶lk♦, and ¶xq↪ xq♦ for each q 6= k.

First, assume that there exists an assignment of the variables V satisfying at least t clauses. From that assignment, we define an alternative d as follows: for all q  p, dq = xq if xq is assigned to true, and dq = xq if xq is assigned to false. Then, we study the number of disagreements between Bi and d. There are two cases to consider:

• ÷ If Ci is satisfied, then either lj is true or lk is true, and from the definition of Bi, we get δ(d↪ Bi) = 0.
• ÷ If Ci is not satisfied, then both lj and lk are false, and from the definition of Bi, we get δ(d↪ Bi) = 1.

Thus, since the assignment satisfies at least k clauses, we have Pni=1 δ(d↪ Bi)  p - t.

Conversely, if there exists a d such that Pni=1 δ(d↪Bi)  p - t, then by a similar line of reasoning as above, we can construct an assignment that satisfies at least t clauses.

On the positive side, there is a model-preserving translation from winner determination for conditional minisum approval voting into maximum satisfiability. We omit the formal details of the general construction but only give an example: the CA ballot B = ¶x↪ x : y↪ x : ¶y↪ y♦♦ is translated into the set of clauses CB = ¶x↪ x _ y↪ x _ y _ y♦ (equivalent to ¶x↪ x _ y♦); then a CA profile P = hB1↪ ▷ ▷ ▷ ↪ Bni is translated into a multi-set of clauses CP = CB1 [▷ ▷ ▷[CBn . For all d 2 D, we have Pi δ(d↪ Bi) = ↵ if and only if the number of clauses that are not satisfied in CP is equal to ↵. 1

This means that conditional minisum approval voting can be solved by off-the-shelf MAXSAT solvers. Moreover, in the case of binary variables with acyclic dependency graphs, it is easy to check that this transformation preserves the differential approximation ratio of 4▷34◁(m+ 4▷34) obtained for MAXSAT in [Escoffier and Paschos, 2007], where m represents the number of clauses. 2

4.4 Properties

We now study some of the properties satisfied by conditional minisum and conditional minimax. Because our rules have CA ballots as input, some of the standard properties have to be adapted. Clearly, our rules satisfy anonymity (the outcome is independent from the identity of voters), and their irresolute versions satisfy value neutrality (the outcome is unchanged after any renaming of the values of some variable) and variable neutrality (the outcome is unchanged after any renaming of the variables). Now we define four other important properties. For two profiles P = (P1↪ ▷ ▷ ▷ ↪ Pn) and Q = (Q1↪ ▷ ▷ ▷ ↪ Qm), we note P +Q = (P1↪ ▷ ▷ ▷ ↪ Pn↪ Q1↪ ▷ ▷ ▷ ↪ Qm).

Definition 6. Let F be a CA irresolute rule.

• ÷ F satisfies reinforcement (resp. weak reinforcement) if for any two profiles P↪Q, if F(P) \ F(Q) 6= ; then F (P + Q) = F (P ) \ F (Q) (resp. ◆ F (P ) \ F (Q)).
• ÷ F satisfies monotonicity if for any profile P = (B1↪ ▷ ▷ ▷ ↪Bn), if d = (x1↪ ▷ ▷ ▷ ↪ xp) 2 F(P) and B0i

1 The translation works also for nonbinary variables, but is more complex, as there is one propositional variable per value di 2 Di, and a feasibility constraint ensures that each variable takes exactly one value. More generally, when D⇤ is a strict subset of D↪ the feasibility constraints are expressed as propositional formulas, and are in sufficiently many copies so as to be 'protected'.

2 Given an instance I of a combinatorial optimization problem, the differential approximation ratio measures "the relative position of the value of an approximated solution in the interval between the value of a worst feasible solution of I, and the value of a best solution of I" [Escoffier and Paschos, 2007].

is obtained from Bi by adding xj to the set of values of Xj approved conditioned on dParGi (Xj), then d 2 F(B1↪ ▷ ▷ ▷ ↪ Bi-1↪ B0i ↪ Bi+1↪ ▷ ▷ ▷ ↪ Bn).

The following properties, participation and strategyproofness, are defined only for resolute rules. 3 Moreover, they require a voters' preference ⌫i to be induced from her CA ballot. We say that a voter with CA ballot Bi has δ-induced preferences if for all x↪ y 2 D⇤ , x ⌫i y if and only if δ(x↪B)  δ(y↪ B). δ-induced preferences generalize Hamming-induced preferences [C¸ uhadaro˘glu and Lain´e, 2012].

Definition 7. Let F T the resolute version of some irresolute rule F, for some tie-breaking mechanism T. F T satisfies

• ÷ F T satisfies δ-participation if for any CA profile P = (B1↪ ▷ ▷ ▷ ↪Bn) and CA ballot Bn+1, we have δ(F T (P + ¶Bn+1♦)↪ Bn+1)  δ(F T (P )↪ Bn+1).
• ÷ F T satisfies δ-strategyproofness if for any CA profile P = (B1↪ ▷ ▷ ▷ ↪ Bn) and CA ballot B0i ,

We have the following results for conditional minisum and minimax. All proofs are simple (we omit them).

Proposition 2.

• ÷ CondMinSum satisfies reinforcement.
• ÷ CondMinMax does not satisfy reinforcement, but satisfies weak reinforcement.
• ÷ CondMinSum and CondMinMax satisfy monotonicity.
• ÷ for any T, CondMinSumT and CondMinMaxT satisfy δ-participation.

Since minimax approval voting [Caragiannis et al., 2010] is manipulable, this is a fortiori the case for CondMinMaxT . On the other hand, simple approval voting (or 'minisum') is strategyproof; however, as soon as preferences are conditional, strategyproofness is lost:

Proposition 3. CondMinSumT is δ-manipulable, even for two binary variables.

Proof. Without loss of generality, assume T favors x1x2 over x1x2. Consider the two-voter CA profile consisting of one ballot ¶x1↪ x1 : x2↪ x1 : x2♦ and one ballot ¶x1↪ x1 : x2↪ x1 : x2♦. The outcome is x1x2. Now, if the second voter casts the ballot ¶x1↪ x1 : x2↪ x1 : x2♦ instead, then the outcome is x1x2, which is her preferred alternative under the assumption that her preferences are δ-induced.

5 Sequential conditional approval voting

For the sake of simplicity, in this section we assume that D⇤ = D (handling feasibility constraints is possible but makes the definitions more complicated).

Sequential conditional approval voting (SCAV) is an approval-based version of sequential voting in combinatorial domains [Lang and Xia, 2009]. Its intuitive principle is that decisions are taken variable by variable, following a fixed order; for each variable, the winning value is the one that has the maximal approval score given the values of the variables that come before it. The SCAV rule is defined only for CA profiles whose dependency graph is compatible with a given order O of the variables. In the rest of this section, O = X1 > ▷ ▷ ▷ > Xp is a fixed order over X .

3 For irresolute rules, we would require to first define a preference extension principle (see, e.g., [Brandt and Brill, 2011] for strategyproofness and [Brandl et al., 2015] for participation).

Definition 8 (O-legal conditional approval profile). A CA ballot is O-legal if its dependency graph contains no edge from Xj to Xi with i < j. A CA profile is O-legal if it is composed of O-legal CA ballots.

Definition 9. The sequential conditional approval voting rule (SCAV) is the rule defined on O-legal CA profiles as follows. Let AppTi be the standard approval voting rule on Di, together with a tie-breaking mechanism Ti, and T = (T1↪ ▷ ▷ ▷ ↪ Tp). For each O-legal P = (B1↪ ▷ ▷ ▷ ↪Bn), let P #Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 = (B#Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 1 ↪ ▷ ▷ ▷ ↪ B#Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 n ); then SCAV T (P) = (x⇤1 ↪ ▷ ▷ ▷ ↪ x⇤p ), where

• ÷ x⇤1 = AppT1 (P #X1 );
• ÷ for each i = 2↪ ▷ ▷ ▷ ↪ p, x⇤i = AppTi (P #Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 ).

A cheap protocol for SCAV T is composed of p rounds: at round i, it elicits only the voters' approval ballots B#Xi ♣x⇤1 ↪▷▷▷↪x⇤i-1 j . Thus, the communication complexity of SCAV T is O(pnmaxi ♣Di♣).

Similarly, we define the SCAV irresolute rule: SCAV (P) is the set of all (x1↪ ▷ ▷ ▷ ↪ xp) such that x1 2 App(P #X1 ) and for all i = 2↪ ▷ ▷ ▷ ↪ p, xi 2 App(P #Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 ). 45

Example 2 (continued). Let O = X1 > X2. The approval scores for m, f and v are respectively 13, 12 and 10: the (unique) selected value for X1 is m. Given X1 = m, the approval scores for r, w and b are respectively 12, 4 and 7: the selected value for X2 is r. The outcome is mr.

For irresolute SCAV, some winning alternative can be computed in polynomial time, and determining whether a given alternative is a winner is also polynomial-time computable: at each round, it suffices to check that xi 2 App(P #Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 ). Also, winner determination is polynomial for resolute SCAV (with a polynomial-time computable tie-breaking mechanism).

Recall that winner determination for conditional minisum is NP-hard, even for an O-legal profile. Moreover, both conditional minisum and SCAV coincide with simple approval voting when restricted to separable profiles. Thus, we may wonder how good an approximation SCAV is to conditional minisum. The approximation ratio is different whether we measure the quality of an alternative by its number of disagreements Pi δ(·↪Bi) (to be minimized) or its number of agreements Pi (p - δ(·↪ Bi)) (to be maximized):

5 Note that the restriction of SCAV to separable profiles coincides with simple approval voting.

4 Note that writing B#Xi♣x⇤1 ↪▷▷▷↪x⇤i-1 j is a slight abuse of notation, since O-legality implies only that ParGj (Xi) ✓ ¶X1↪ ▷ ▷ ▷ ↪ Xi-1♦.

Proposition 4. Consider a combinatorial domain with p variables X1↪ ▷ ▷ ▷ ↪Xp with ♣Di♣ = ↵i for all i.

• ÷ The largest possible ratio, over all O-legal CA profiles, between the agreement score of the conditional minisum winner and the agreement score of the SCAV winner, is ( 1 ↵1 +p-1)◁ Ppi=1 1 ↵i .
• ÷ The largest possible ratio, over all O-legal CA profiles, between the disagreement score of the SCAV winner and the disagreement score of the conditional minisum winner, is Ppi=1 (1- 1 ↵i )◁(1- 1 ↵1 ).

Proof sketch. Consider n CA ballots, with the dependency graph whose edges are ¶Xi ! Xj ♣ 1  i < j  p♦. First, we look for an upper bound of the disagreement score of an alternative that wins for SCAV. Assume that (x11x21 ▷ ▷ ▷ xp1 ) is the winning alternative for SCAV. Then, for (x11x21 ▷ ▷ ▷ xp1 ) to be winning for SCAV, x11 , respectively x11 : x21 , . . . , x11x21 ▷ ▷ ▷ : xp1 , has to be approved by at least n◁↵1 voters, respectively n◁↵2↪ ▷ ▷ ▷ ↪ n◁↵p voters. It leads to a maximal disagreement score of n · Ppi=1 1 - 1◁↵i.

Thus, we get a worst-case ratio of (Ppi=1 1 - 1◁↵i)◁(1 - 1◁↵1). This ratio is reached on a CA profile for which there is a perfect split between all values of X1 (with each voter approving only one value), and then, conditionally on the value chosen for X1 (by tie-breaking), there is also a perfect split for each other variable, while for some of the other values of X1, there is a perfect agreement between all voters on all other variables. The same profile shows that the bound relative to the number of agreements is reached too.

Now, we look for a lower bound for the disagreement score of a winning alternative for conditional minisum, under the condition that it is winning for SCAV. Assume that (x12x22 ▷ ▷ ▷ xp2 ) is a winning alternative for conditional minisum. One way to avoid this alternative to be a SCAV winner is by eliminating it at the first round of the sequential vote. It implies that x12 has to be approved by less than n ↵1 voters, and, in this case, x12 : x22 ↪ ▷ ▷ ▷ ↪ x12x22 ▷ ▷ ▷ : xp2 can be approved by any number of voters, and then, the disagreement score for (x12x22 ▷ ▷ ▷ xp2 ) without being a winner for SCAV is at least n- n ↵1 . There exist other ways to avoid (x12x22 ▷ ▷ ▷ xp2 ) to be a winning alternative for SCAV, but they lead to disagreement scores that are at least as large as that one. The proof for the bound relative to the agreement score is similar.

In particular, when all domains have the same cardinality ↵, then these ratios become p and (1 + (p - 1)↵)◁p, and in the case of binary domains, p and 2 - 1◁p.

Proposition 5. SCAV satisfies anonymity, neutrality, reinforcement and monotonicity. For any tie-breaking mechanism T, SCAVT does not satisfy δ-participation.

Corollary 1. If the quality of a solution is measured by the number of disagreements, then SCAV is a Ppi=1 (1 - 1 ↵i )◁(1 - 1 ↵1 )-approximation of CondMiniSum. If it is measured by the number of disagreements, then it is a ( 1 ↵1 +p-1)◁ Ppi=1 1 ↵i -approximation of CondMiniSum.

Proof. Anonymity and neutrality are obvious. Reinforcement and monotonicity are easily proven by induction on the variables, and using the fact that standard approval voting satisfies them. For participation, consider the two-voter CA profile P = hB1↪B2i with B1 = ¶x1↪ x2↪ x3♦ and B2 = ¶x1↪ x2↪ x3♦. Assume without loss of generality that T favors x1x2x3 over x1x2x3, thus F T (P) = x1x2x3. Now, consider a third voter with preferences δ-induced by B3 = ¶x1↪ x1 : x2↪ x1 : x2↪ x1 : x3↪ x1 : x3♦. If she votes, the outcome is x1x2x3, which has only one agreement with her ballot, while x1x2x3 had two.

Proposition 6. For any tie-breaking mechanismT, SCAVT is not δ-strategyproof for p ≥ 3 (even for binary variables), and is strategyproof for two variables.

Proof. For p = 3, consider the profile in the proof of Proposition 5. If the third voter expresses his sincere ballot ¶x1↪ x1 : x2↪ x1 : x2↪ x1 : x3↪ x1 : x3♦, the outcome is x1x2x3. If he expresses instead the ballot ¶x1↪ x1 : x2↪ x1 : x2↪ x1 : x3↪ x1 :x3♦ the the outcome is x1x2x3, which he prefers.

For p = 2, let X = ¶X1↪X2♦; suppose that voter i with sincere ballot B has a manipulation B0 ; let x⇤ be the outcome for her sincere vote and x+ the outcome after manipulation. Since B0 is a manipulation and i has δ-induced preferences, we have δ(x+↪B0 ) < δ(x⇤ ↪B). This implies (1) δ(x+↪B0 ) < 2 and (2) δ(x⇤ ↪B) > 0. Once the value of X1 has been fixed, we are left with a standard approval vote on X2 and i cannot obtain a better outcome than the sincere outcome; therefore, the manipulation has to bear on X1 and has to change the value of X1, from, without loss of generality, x1 to x01 , with i initially approving x1 but not x01 . But this implies that δ(x+↪B0 ) ≥ 1 and δ(x⇤ ↪B)  1, which together with (1-2) implies δ(x+↪B0 ) = δ(x⇤ ↪B) = 1, therefore i, who has δ-induced preferences, cannot prefer x+ to x⇤ .

6 Conclusion

We have generalized approval voting to combinatorial domains and to nonseparable preferences. Our rules are natural generalizations of simple (or 'minisum') and minimax approval voting. They can be applied for all types of voting on combinatorial domains. Conditional minisum and minimax are computationally hard, but conditional minisum can be solved by MaxSAT solvers. Sequential conditional AV is easy to compute. Our rules (especially conditional minisum) satisfy a number of important properties.

There are other rules for multiwinner elections using approval ballots, where the satisfaction of a voter is not simply the Hamming distance to his preferred outcome (see [Kilgour, 2010] for a survey, and [Aziz et al., 2015b] for their computation). These rules could be adapted to CA ballots in the same way as we did for simple and minimax approval voting. The rules defined in [Amanatidis et al., 2015], where the dissatisfaction degrees of the voters is aggregated by ordered weighted averages intermediate between max and sum, could also be generalized to CA ballots.

Acknowledgement

We thank Bernard Ries for helpful discussions. This research has been supported by the project ANR-14-CE24-0007-01 CoCoRICo-CoDec.