Jérôme Lang
email: lang@lamsade.dauphine.fr

Jérôme Mengin
email: jerome.mengin@irit.fr

Lirong Xia
email: xialirong@gmail.com

Voting on multi-issue domains with conditionally lexicographic preferences ✩

Keywords:

One approach to voting on several interrelated issues consists in using a language for compact preference representation, from which the voters' preferences are elicited and aggregated. Such a language can usually be seen as a domain restriction. We consider a well-known restriction, namely, conditionally lexicographic preferences, where both the relative importance between issues and the preference between the values of an issue may depend on the values taken by more important issues. The naturally associated language consists in describing conditional importance and conditional preference by trees together with conditional preference tables. In this paper, we study the aggregation of conditionally lexicographic preferences for several common voting rules and several classes of lexicographic preferences. We address the computation of the winning alternative for some important rules, both by identifying the computational complexity of the relevant problems and by showing that for several of them, computing the winner reduces in a very natural way to a maxsat problem.

Introduction

There are many situations where a group of agents has to make a common decision in multi-issue domains, i.e. a set of possibly interrelated binary issues. A typical example of such a situation is that of multiple referenda: there is a set of binary issues (such as building a sport centre, building a cultural centre etc.), and the group must make a yes/no decision on each of them [START_REF] Brams | The paradox of multiple elections[END_REF]. Another example is group product configuration, where the group must agree on a complex object consisting of several components, each taking one of two possible values.

Voting on several interrelated issues is a challenging problem. If the agents vote separately on each issue, then paradoxes generally arise [START_REF] Brams | The paradox of multiple elections[END_REF][START_REF] Lacy | A problem with referenda[END_REF]. Such paradoxes rule out this 'decompositional' approach, except in the very restricted case when voters have separable preferences. A second way consists in using a sequential voting protocol: issues are considered one after another, in a predefined order, and the voters know the assignment to the earlier variables before expressing their preferences on later ones (see, e.g., [START_REF] Lang | Sequential composition of voting rules in multi-issue domains[END_REF][START_REF] Pozza | Multi-agent soft constraint aggregation via sequential voting[END_REF][START_REF] Airiau | Aggregating dependency graphs into voting agendas in multi-issue elections[END_REF]). This method, however, works reasonably well only if we can guarantee that there exists a common order over issues such that every agent can express her preferences unambiguously on the values of each issue at the time she is asked to report them.

A third class of methods consists in using a language in which the agents can express their preferences over the space of combined alternatives for all issues simultaneously. If the language is expressive enough to allow for expressing any possible preference relation, then the aforementioned paradoxes are avoided. However, this expressivity implies significant elicitation and computation costs: in a multi-issue domain, the number of alternatives is exponential in the number of issues, therefore the number of possible preference relations is doubly exponential and whichever language we use to represent them, the input will be exponential in the worst case. One way around this problem is to use some compact preference representation language; this comes at the cost of some domain restriction, depending on the chosen language.

Therefore, when aggregating preferences on multiple interrelated issues, a choice, or a trade-off, must be made between (a) being prone to severe paradoxes, (b) requiring a heavy communication and computation burden or (c) imposing a domain restriction.

In this paper, we explore a particular domain restriction by focusing on conditionally lexicographic preferences. Standard lexicographic preferences are a simple model, where alternatives are first sorted according to one issue, considered to be the most important one; alternatives that have equal values for that issue are then sorted according to the second most important issue, and so on until the set of alternatives is totally ordered. The psychology literature shows evidence that lexicographic preferences are often an accurate model for human decisions [START_REF] Gigerenzer | Reasoning the fast and frugal way: models of bounded rationality[END_REF][START_REF] Schmitt | On the complexity of learning lexicographic strategies[END_REF]. Although very intuitive, this model is quite restrictive. However, it can be extended by allowing the preferences over the values of an issue, as well as the relative importance of two issues, to depend on the values of more important issues. The relative importance of issues is no longer a linear ordering, but a tree, with the most important issue at its root. A preference relation is conditionally lexicographic if it is defined by such a lexicographic preference tree. To the best of our knowledge, conditionally lexicographic preference trees were first introduced by Fraser [START_REF] Fraser | Applications of preference trees[END_REF][START_REF] Fraser | Ordinal preference representations[END_REF], and have been considered in individual decision making (and especially in constraint satisfaction problems) by Wilson [START_REF] Wilson | An efficient upper approximation for conditional preference[END_REF][START_REF] Wilson | Efficient inference for expressive comparative preference language[END_REF] and Wallace and Wilson [START_REF] Wallace | Conditional lexicographic orders in constraint satisfaction problems[END_REF], as well as, from the learning point of view, by Booth et al. [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF], Brauning et al. [START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF][START_REF] Bräuning | Lexicographic preferences for predictive modeling of human decision making: a new machine learning method with an application in accounting[END_REF] and by Liu and Truszczy ński [START_REF] Liu | Learning partial lexicographic preference trees over combinatorial domains[END_REF]. Note that Wilson [START_REF] Wilson | Efficient inference for expressive comparative preference language[END_REF] and Brauning et al. [START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF][START_REF] Bräuning | Lexicographic preferences for predictive modeling of human decision making: a new machine learning method with an application in accounting[END_REF] propose to extend further the lexicographic preference model by allowing several variables to appear at the same importance level/node in the tree; we do not consider such trees in this paper.

Lexicographic preferences appear to be a reasonable assumption in many domains (see the work of Taylor [START_REF] Taylor | The problem of salience in the theory of collective decision-making[END_REF] for a discussion on the plausibility of lexicographic preferences in various political contexts). However, it implies a strong domain restriction: for q binary variables, there are (2 q )! preference relations and only 2 q (respectively q! × 2 q ) lexicographic preference relations if the importance order is fixed (respectively, not fixed). As explained above, domain restrictions are needed to escape strong paradoxes and significant communication cost, but the risk, by making a too strong domain restriction, is to be on the weak side regarding its plausibility, since only a tiny fraction of the whole set of preference relations falls in the class of lexicographic preference relations. (A similar problem occurs with separable preferences.) Conditionally lexicographic preference models still are a domain restriction, but a much weaker one than standard lexicographic preferences, as there are exponentially more conditionally lexicographic preferences than lexicographic preferences [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF]. Therefore, this assumption can be seen as a reasonable trade-off between expressivity and complexity.

The aggregation of lexicographic preferences over combinatorial domains has received only little attention. Taylor [START_REF] Taylor | The problem of salience in the theory of collective decision-making[END_REF] considers the aggregation of lexicographic preferences on a domain of two attributes with real-valued domains. Each voter has unconditional, single-peaked preferences on each of the two attribute domains. He shows that when voters all have the same importance order, there always exists a weak Condorcet winner, but that this is no longer the case if voters may diverge on the relative importance of the two attributes (and he characterizes situations where a weak Condorcet winner exists). Pattanaik [START_REF] Pattanaik | Group choice with lexicographic individual orderings[END_REF] generalizes the former results on domains of more than two attributes, and establishes conditions for the existence of a socially best alternative for a wider class of voting rules including simple majority. Bhadury et al. [START_REF] Bhadury | Finding the majority-rule equilibrium under lexicographic comparison of candidates[END_REF] generalize Taylor's latter result to more than two attributes. Encarnacion [START_REF] Encarnacion | Group choice with lexicographic utility[END_REF] focuses on preference aggregation (with a preference relation as output) rather than voting: he also considers lexicographic preferences with a unconditional importance order, common to all agents, and single-peaked preferences on the domain of each variable, and shows that this domain restriction is Arrow-consistent.

More recently, Liu and Truszczy ński [START_REF] Liu | Aggregating conditionally lexicographic preferences using answer set programming solvers[END_REF] obtained results completing the results we obtained in our conference paper [START_REF] Lang | Aggregating conditionally lexicographic preferences on multi-issue domains[END_REF] (see Section 5 for more discussions) and used answer-set programming to encode and solve preference aggregation problems on combinatorial problems with conditionally lexicographic preferences (we will come back to this in more detail in Section 4).

Dividino et al. [START_REF] Dividino | Ranking RDF with provenance via preference aggregation[END_REF] make use of lexicographic preferences for preference aggregation in multi-attribute domains. A major difference with our work is that they use lexicographicity for the preference aggregation phase and not for defining each of the individual preferences. They start with a set of items (pieces of information on the web), each associated with a tuple of values corresponding to various criteria such as the time the item was posted, its source, etc. Each criterion corresponds to a weak order over items (for instance, for time, the more recent the better). Finally, given an importance order ⊲ on criteria, the global preference relation over items is defined lexicographically according to ⊲.

The generic problem of aggregating conditionally lexicographic preferences can be stated as follows. The set of alternatives is a multi-issue domain D composed of a finite set of binary issues. 1 We have a set of voters, each providing a conditionally lexicographic preference relation over D under the compact and natural form of a lexicographic preference tree (LP-tree for short) [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF], which we will define soon. Therefore, a (compactly represented) profile V consists of a collection of LP-trees. Finally, for a given voting rule r, we ask whether there is a simple way to compute the winner, namely r(V ), where 'simple' means that the winner should be computed efficiently and directly from V . This means that we must avoid producing the entire preference relations of every voter explicitly, which would require exponential space. For many cases where winner determination is computationally hard, we show that these problems can be efficiently converted to maxsat problems and can be solved by maxsat solvers.

The rest of the paper is organized as follows. Conditionally lexicographic preferences and their compact representation by LP-trees are defined and discussed in Section 2. In Section 3 we state the problem considered in this paper, namely the application of voting rules to profiles composed of conditionally lexicographic preferences. We will focus on three families of rules. First, k-approval rules in Section 4: we show that for many values of k, we can give a quite satisfactory answer to our question above, even for our most general models. Note that by 'satisfactory' we do not necessarily mean 'computable in polynomial time'. For instance, we will show that in some cases, there is a model-preserving translation between the winner determination problem and a maximum (weighted or unweighted) satisfiability problem. Since efficient maxsat solvers exist, in such cases we can consider preference aggregation as tractable to some extent. In Section 5 we focus on the Borda rule (and, to a lesser extent, to some other positional scoring rules sharing some properties with Borda): we show that winner determination can be solved in polynomial time for some of the simplest LP-tree models, and propose a translation into a weighted minimum satisfiability problem for some general models. We also provide a natural family of scoring rules for which similar translations exist. Then in Section 6 we consider the existence of a Condorcet winner, and show that even deciding whether a given alternative is a Condorcet winner is hard. In Section 7, we consider a particular setting where all voters have a common, possibly conditional, importance structure among issues, but can have varying, conditional preferences over the values of each issue. Section 8 is devoted to the specific case of LP-trees with fixed local preferences but possibly different structures. In Section 9 we discuss the application of our results to committee elections, as well as the importance of our domain restriction, and the extension of our results to variables with nonbinary domains. Finally, Section 10 concludes.

Conditionally lexicographic preferences and LP-trees

Let I = {X 1 , . . . , X q } (q ≥ 2) be a set of issues, where each issue X i takes a value in a binary local domain D i , denoted as {0 i , 1 i }, or as {x i , x i }, or, when there is no ambiguity, as {0, 1}. The set of alternatives is We first give a high-level description of lexicographic preferences. Any two alternatives d, e are compared by looking at the issues in sequence, according to their importance, until we reach an issue X such that the value of X in d is different from the value of X in e. d and e are then ordered according to the local preference relation over the values of X . For such lexicographic preference relations we need both an importance relation between issues, and local preference relations over the domains of the issues. Both the importance between issues and the local preferences may be conditioned by the values of more important issues. Such lexicographic preference relations can be compactly represented by Lexicographic Preference trees (LP-trees) [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF], formally defined in the upcoming subsection.

D = D 1 × • • • × D q , that

Lexicographic preference trees

An LP-tree L is composed of two parts:

1. A tree T where each node t is labelled by an issue, denoted by Iss(t) = X i , such that every issue appears once and only once on each branch; each non-leaf node either has two outgoing edges, labelled by the two values in the local domain (0 i and 1 i ) respectively, or one outgoing edge, labelled by {0 i , 1 i }.

0 i ≻ 1 i or u : 1 i ≻ 0 i .
An LP-tree L represents a linear order ≻ L over D as follows. Let X i be the issue associated with the root of L, and let ≻ X i denote the associated local preference relation. We denote by L X i =x i (respectively L X i =x i ) the subtree of L corresponding to 1 The assumption that issues (or variables) are binary is made for the sake of simplicity, and because it holds in many practical domains, especially multiple referenda (see [START_REF] Lang | Voting in combinatorial domains[END_REF]). We discuss the extension of our results to non-binary domains in Subsection 9.3.

L P 1 L P 2 L P 3 L P 4 M m≻m F f ≻ f P p ≻ p P p ≻ p F p : f ≻ f p : f ≻ f m m P p ≻ p F f ≻ f M p :m≻m p :m≻m F f ≻ f M m≻m P p ≻ p P p ≻ p M m≻m f f P p ≻ p F f ≻ f M m≻m Fig. 1. Four LP-trees.
the branch

X i = x i (respectively X i = x i ). Let d = (d 1 , . . . , d q
) and e = (e 1 , . . . , e q ) be two different alternatives. Then d ≻ L e if either (1) d i ≻ X i e i , or (2)

d i = e i and d ≻ L X i =d i e.
Moreover, to each alternative d ∈ D corresponds a single branch in the tree: at each node labelled with issue X i with two outgoing edges, the branch corresponding to d follows the edge labelled with d i . The importance order associated with d in L, denoted by IO(L, d), is the order in which issues appear along that branch. We use ⊲ to denote an importance order to distinguish it from agents' preferences ≻ over D. If in L each node has no more than one child, then all alternatives are associated with the same importance order ⊲, and we say that ⊲ is the importance order of L.

The size |L| of an LP-tree L is the number of its nodes plus the accumulated size of its conditional preference tables. Note that the size of L may be exponential in q even in the case of a linear structure.

Example 1. Suppose there are three binary issues to be decided among the inhabitants of a city.

1. Should the city build a metro? 2. Should the city centre be pedestrian? 3. Should there be a fee for cars entering the city?

The three issues are M (metro) with domain {m, m}, P (pedestrian) with domain {p, p}, and F (fee) with domain { f , f }.

There are four voters. Each voter has conditionally lexicographic preferences represented by the LP-trees L P 1 , L P 2 , L P 3 and L P 4 respectively as depicted in Fig. 1.

Consider the LP-tree L P 1 . Let P 1 be the node at the extremity of the left branch. We have Iss(P 1 ) = P, Anc(P 1 ) = {M, F}, Inst(P 1 ) = {M}, NonInst(P 1 ) = {F}, and Par(P 1 ) = ∅ because the preferences over {p, p} do not depend on the value of F. On the other hand, if F 1 is the node at the extremity of the right branch, then Par(F 1 ) = {P}. The linear order represented by

L P 1 is mf p ≻ mf p ≻ m f p ≻ m f p ≻ mp f ≻ mp f ≻ mp f ≻ mp f . Moreover, IO(L P 1 , mf p) = [M ⊲ F ⊲ P] and IO(L P 1 , m f p) = [M ⊲ P ⊲ F].
We say that an LP-tree has unconditional local preferences when the preference relation on the value of every issue is independent from the values of all other issues. In other words, each issue in the tree only contains unconditional preferences. This is the case for trees L P 3 and L P 4 but not for L P 1 nor L P 2 . In L P 1 , for instance, the preference between p and p depends on the value of M. We note that when the preferences are unconditional it is still possible that the importance relation be conditional, i.e. the tree may have branches.

Likewise, we say that the importance relation is unconditional when the order of the issues is the same in all branches of the tree (or, equivalently, when the tree has a single branch). This is the case of trees L P 2 and L P 4 . Note that L P 4 has both unconditional importance and unconditional local preferences. See [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF] for a discussion on various sub-classes of LP-trees.

A property that makes LP-trees appealing for social choice is that it is easy to compute the rank of alternatives:

Observation 1. Consider an alternative d and an LP-tree L. For each issue X i , let t i be the node labelled with X i in the branch of L corresponding to d; we can define the level of X i w.r.t. d and the local rank of d w.r.t. to X i as follows:

• level(L, d, X i ) is the level of t i in the tree, that is, the distance from t to the root plus one. The level of the root is 1 and the level of all leaves is q.

• (L, d, X i ) is the local rank of the value of d for issue X i in the local preference at t i . Because issues are binary, (L, d, X i ) = 0 if d i ≻ d i at node t i (given the values of d for the issues that appear above t i ), and (L, d, X i ) = 1 otherwise.

Let rank(L, d) be the rank of d in the linear order ≻ L defined by L, then:

rank(L, d) = 1 + q i=1 2 q-level(L,d, X i ) (L, d, X i ) (1)
Example 2. Consider L P 1 defined in Example 1.

rank(

L P 1 , mf p) = 1 + 2 2 × 0 + 2 1 × 0 + 2 0 × 0 = 1; rank(L P 1 , m f p) = 1 + 2 2 × 1 + 2 1 × 1 + 2 0 × 1 = 8; rank(L P 1 , m f p) = 1 + 2 2 × 0 + 2 1 × 1 + 2 0 × 1 = 4.
Note that rank(L, d) can be computed by a simple top-down traversal of L along the branch corresponding to d, in time linear in the number of issues.

Conversely, Algorithm 1 computes the alternative with rank k in the linear order ≻ L corresponding to an LP-tree L: the base 2 representation of k -1 is used to guide a top-down traversal of the tree from the root to a leaf. The running time is again linear in the number of issues.

Algorithm 1: F ind Alternati ve(L, k).

1 Let k -1 = (k q-1 ...k 0 ) 2 and L * = L; 2 for i = q -1 down to i = 0 do 3 Let X i be the root issue of L * . Let the local preferences be x i ≻ x i ;

4 if k i = 1 then 5 L * ← L * X i =x i ; d i ← x i ; 6 else 7 L * ← L * X i =x i ; d i ← x i ;

Applying voting rules to LP-trees

A (voting) profile V over a set of alternatives D is a collection of n votes V 1 , . . . , V n , each being a linear order on D. An (irresolute) voting rule r maps every profile V to a nonempty subset of D: r(V ) is the set of co-winners for V under r. A scoring function S is a mapping from L(D) n × D to R. Often, a voting rule r is defined in such a way that r(V ) is the set of alternatives maximizing some scoring function S r . In particular, a positional scoring rule is defined by a scoring vector v = (v(1), . . . , v(m)), where m is the number of alternatives (in this paper m = 2 q ): for any vote V i ∈ L(D) and any c ∈ D, let S v (V , c) = v(rank V (c)), where rank V i (c) is the rank of c in V i . Then for any profile

V = (V 1 . . . , V n ), let S v (V , c) = n j=1 S v (V j , c
). The winner is the alternative maximizing S v (V , •). In particular, the k-approval rule App k (with k ≤ m), is defined by the scoring vector v [START_REF] Brams | The paradox of multiple elections[END_REF]

= • • • = v(k) = 1 and v(k + 1) = • • • = v(m) = 0. Let S k
App denote scoring vector for k-approval. The Borda rule is defined by the scoring vector (m -1, m -2, . . . , 0). Let S Borda denote the scoring vector for Borda, that is,

S Borda (V i , c) = m -rank V i (c).
Let N V (c, d) denote the number of votes in V that rank c ahead of d. An alternative c is the Condorcet winner for a profile V if for every d = c, a (strict) majority of votes in V prefers c to d, that is, if N V (c, d) > n/2. If for every d = c we have N V (c, d) ≥ n/2, with equality for at least one d, then c is a weak Condorcet winner.

Voting restricted to conditionally lexicographic preferences

Applying a voting rule to profiles consisting of arbitrary preferences on multi-issue domains is highly unpractical, because the specification of such preferences requires exponential space if no domain restriction is made. Does it become significantly easier when we restrict to conditionally lexicographic preferences? This is the key problem addressed in this paper. Of course the answer depends on the voting rule used.

A conditionally lexicographic profile is a collection of n conditionally lexicographic preferences over D. As conditionally lexicographic preferences are compactly represented by LP-trees, we define an LP-profile V as a collection of n LP-trees.

Given an LP-profile V and a voting rule r, a naive way of finding the co-winners would consist in determining the n linear orders induced by the LP-trees and then applying r to these linear orders. However, this would be very inefficient, both in space complexity and time complexity. Therefore, we would like to know if it is feasible, and efficient, to compute the winners directly from the LP-trees. More specifically, we ask the following questions: (a) given a voting rule, how difficult is it to compute the co-winners (or, else, one of the co-winners) for various classes of LP-trees? (b) for score-based rules, how difficult is it to compute the score of the co-winners? Formally, for each voting rule r defined as the maximizer of scoring function S, we consider the following decision and function problems.

EVALUATION (for r):

Input

LP-profile V , integer number T Question Does there exist an alternative d such that S(V , d) > T ?

WINNER (for r):

Input LP-profile V Output r(V )
Note that if evaluation is NP-hard and the score of an alternative can be computed in polynomial time, then winner cannot be in P unless P = NP: if winner were in P, then evaluation could be solved in polynomial time by computing a winner and its score. For the voting rules studied in this paper, if not mentioned specifically, evaluation is w.r.t. the score functions we present when defining these rules.

LP-trees and propositional logic

Some of the positive results in the sequel are obtained by translating LP-trees into some particular types of logical formulas. We briefly recall here some basic notions of propositional logic and some satisfiability problems that will be used in the sequel.

Given a set of propositional symbols P, logical formulas can be built with the usual connectives ∧ (conjunction), ∨ (disjunction) and ¬ (negation). In several translations, we will use one propositional symbol for each issue, and so we will use the same notation for an issue X i and the corresponding propositional symbol, so that the set of propositional symbols will often be I itself.

The literals are the elements of P and their negations; that is, the set of literals is {X, ¬X | X ∈ P}. A clause has the general form C = l 1 ∨ l 2 ∨ . . . ∨ l |C| , where each l i is a literal. When all the literals, except possibly one, are negated propositions, it is a Horn clause. A dual of a clause is a cube, which is a conjunction of literals.

A valuation of P assigns a Boolean value 0 (false) or 1 (true) to each symbol in P. A valuation satisfies a clause if it makes at least one literal true, and sat is the problem of deciding if a given set of clauses is satisfiable, that is, if there is at least one valuation that satisfies all clauses; such a valuation is called a model of the set of clauses. sat is an NP-complete problem.

The maxsat problem is a generalization of sat: given a set of clauses, we want to find a valuation maximizing the number of satisfied clauses. In the partial weighted maxsat problem, some clauses have an associated positive weight, the others are left unweighted; the goal is to maximize the sum of the weights of the satisfied weighted clauses, while satisfying all the unweighted clauses. These are NP-complete problems, but the 2016 maxsat Evaluation, part of the 19th International Conference on Theory and Applications of Satisfiability Testing, shows that some solvers are able to solve industrial benchmarks in a few minutes, with up to hundreds of thousands of variables, and millions of clauses (of size 3). 2Some of the most competitive solvers, at the time of writing, are described in e.g. [START_REF] Abramé | AHMAXSAT: Description and evaluation of a branch and bound Max-SAT solver[END_REF][START_REF] Martins | Open-wbo: a modular maxsat solver[END_REF][START_REF] Luo | CCLS: an efficient local search algorithm for weighted maximum satisfiability[END_REF]. In the generalized maxsat problem, the input is not restricted to clauses: given a set of propositional formulas, we want to find a valuation that satisfies as many of the formulas as possible.

weighted minsat is another variant of sat: given a set of clauses, each associated with a positive cost, we want to find a valuation with minimum cost, where the cost of a valuation is the sum of the weights of the clauses that it satisfies. Although it is NP-complete, this problem too can be solved using efficient solvers; some work by translating these instances into weighted maxsat instances (e.g. [START_REF] Kügel | Natural max-sat encoding of min-sat[END_REF][START_REF] Zhu | A new encoding from minsat into maxsat[END_REF]), whereas more recent ones use branch-and-bound techniques directly on the minsat instances (see, e.g. [START_REF] Li | Optimizing with minimum satisfiability[END_REF][START_REF] Argelich | MinSAT versus MaxSAT for optimization problems[END_REF]). [START_REF] Li | Optimizing with minimum satisfiability[END_REF] reports on experiments where random minsat instances with one hundred variables and up to five times more clauses were solved in a few minutes. According to [START_REF] Argelich | MinSAT versus MaxSAT for optimization problems[END_REF], the performances of minsat solvers seem to be comparable to that of maxsat solvers, some particular problems being more efficiently solved with one or the other.

k-Approval

Recall that it is possible to compute, in time linear in the number of issues, the k-th ranked issue of any LP tree for any k (cf. Algorithm 1). Therefore, given an integer k < 2 q and an LP profile V , we can compute the top k alternatives of all LP-trees in V , and store them in a table together with their k-approval scores. As we have at most kn such alternatives, constructing the table takes time in O (knq). Hence we have the following result.

Proposition 2. For any constant k, given an LP-profile V with n voters, the k-approval co-winners for V can be computed in time in O (knq).

Example 3. Let V be the profile of Example 1. The winners for 1-approval (that is, plurality) are mf p, m f p, m f p and m f p -their 1-approval score is 1. The winners for 2-approval are m f p and m f p, with a 2-approval score of 2.

A similar result also holds for computing the (2 qk)-approval co-winners for any constant k. However, unless q is very small, there is little practical interest in using (2 qk)-approval for a fixed (small) value of k, since in practice, we expect kn ≪ 2 q , so that almost every alternative would be a co-winner.

We now focus on k-approval voting for values of k that are defined via proportions of the number 2 q of alternatives.

Let M ≤ q be a positive integer and define Rat(M) as the set of all rational numbers of the form j/2 M for some positive integer M and j ∈ {1, . . . 2 M -1}. Equivalently, Rat(M) is the set of all numbers α in the interval (0, 1) with a finite base 2 representation of length at most M. For any α ∈ Rat(M), α-proportion-approval is another name for the α2 q approval rule.

We first consider 1 2 -proportion-approval, or, equivalently, 2 q-1 -approval. This rule requires to count the top 50% alternatives, which corresponds to the 'better' half of the tree. In this case, each voter only has to communicate her most important issue and its preferred value. Applying 2 q-1 -approval here is therefore both intuitive and cheap in communication, and it turns out that the co-winners can be represented compactly and computed very easily. Theorem 3. Winner for 2 q-1 -approval and LP-profiles can be computed in time O (nq).

Proof. An alternative d is among the first half of alternatives in an LP-tree L j if and only if the root issue of L j is assigned to its preferred value. We build a table with the following 2q entries {1 1 , 0 1 , . . . , 1 q , 0 q }: for every L j we add 1 to the score of 1 i (resp. 0 i ) if X i is the root issue of L j and the preferred value is 1 i (resp. 0 i ). When this is done, for each X i , we instantiate X i to 1 i (resp. 0 i ) if the score of 1 i is larger than the score of 0 i (resp. vice versa); if the scores are identical, we do not instantiate X i . We end up with a partial instantiation, whose set of models (satisfying valuations) is exactly the set of co-winners. ✷ Example 4. Let V be the profile consisting of the 4 LP-trees of Example 1: P is the most important issue for two voters, both with preferred value p; M is the most important issue for one voter with preferred value m, and F is the most important issue for one voter with preferred value f : therefore, the 4-approval winner is mf p. If we add to this profile a fifth LP-tree with most important issue M and preferred value m then M will not be instantiated, and the two cowinners will be mf p and m f p.

While 1 2 -proportion-approval takes into account only the most important issue of each voter together with his preferred value, 1 4 -and 3 4 -proportion approval take into account the most important two issues of each voter; 1 8 -, 3 8 -, 5 8 -and 7 8 take into account the most important three issues of each voter, and so on.

We now give a practical way to compute the α-proportion-approval co-winners, using a translation of the problem into an instance of generalized maxsat, with a one-to-one correspondence between the solutions of the voting problem and the solutions of its translation (which is usually referred to as a "model-preserving translation"). Using a reverse translation, we will then prove that, for any α ∈ Rat(M) \ { 1 2 }, α-proportion-approval is in fact NP-hard. To illustrate the idea we first give the construction for two special cases: α = 1/4 and α = 3/4. Consider first the case α = 1/4 and some LP-tree L j whose top issue is X i 1 with preferred value x i 1 ∈ {0 i 1 , 1 i 1 }. Assume that the second most important issue given x i 1 is X i 2 , with preferred value x i 2 . Then, the 1 4 2 q best alternatives are those that have precisely values x i 1 and x i 2 for X i 1 and X i 2 respectively. We can encode these alternatives by a formula l i 1 ∧ l i 2 , whose models are precisely the 1 4 2 q best alternatives for L j : if x i 1 = 1 i 1 then we let l i 1 = X i 1 , and otherwise l i 1 = ¬X i 1 ; l i 2 is defined similarly.

Consider now the case α = 3/4 and some LP-tree L j whose top issue is X i 1 with preferred value x i 1 and whose second most important issue given x i 1 is X i 2 , with preferred value x i 2 in this case: the 3 4 2 q best alternatives are those for which

X i 1 = x i 1 and those for which X i 1 = x i 1 and X i 2 = x i 2 .
These alternatives can be encoded as the models of the formula

l i 1 ∨ l i 2 ,
where l i 1 and l i 2 are the same as defined above for the case α = 1 4 .

More generally, we define, for LP-tree L over a set I of q issues, and a fraction α ∈ Rat(M), a formula φ(L, α) which characterizes the alternatives that are among the α2 q best alternatives of L. We note that, since q ≥ M, α2 q is an integer number. Let X i be the root issue, let x + i be the preferred value for X i , and x - i be its less preferred value; let l i = X i if

x + i = 1 i , and l i = ¬X i if x + i = 0 i , then: φ(L, α) =    l i ∧ φ(L + , 2α) if 0 < α < 1/2 l i if α = 1/2 l i ∨ φ(L -, 2α -1) if 1/2 < α < 1 where L + (respectively L -) is the subtree of L corresponding to x + i (respectively x - i )
, with the local preference tables being simplified by removing all conditional preferences where

X i = x - i (respectively X i = x + i ).
The translations for LP tree L P 1 for two values of α are shown on Fig. 2.

Proposition 4. Let α ∈ Rat(M). Let V be an LP-profile over a set I of q ≥ M issues. Let V = {φ(L j , α) | L j ∈ V } be the multiset of formulae associated with V (note that the same formula can appear in several copies in V ). Then the α-proportion-approval co-winners are the valuations (i.e., truth assignments) over I that maximize the number of formulas satisfied in V .

M m≻m F f ≻ f P p ≻ p P p ≻ p F p : f ≻ f p : f ≻ f m m φ(L P 1 , 3 8 )=M ∧φ(L P 1 1 , 3 4 ) φ(L P 1 1 , 3 4 )= F ∨φ(L P 2 1 , 1 2 ) φ(L P 2 1 , 1 2 )=¬P φ(L P 1 , 5 8 )=M ∨φ(L P 3 1 , 1 4 ) φ(L P 3 1 , 1 4 )= P ∧φ(L P 4 1 , 1 2 ) φ(L P 4 1 , 1 2 )= F L P 1 1 L P 2 1 L P 3 1 L P 4 1 -P = p α=3/8: φ =M ∧(F ∨¬P )
worst acceptable alternative: m f p α=5/8: φ =M ∨(P ∧ F )

worst acceptable alternative: mp f Fig. 2. LP tree L P 1 and its translations into formulas for 3-approval and 5-approval.

Proof. The result follows from the fact that an alternative d is in the α2 q best alternatives of some LP-tree L j if and only if the corresponding valuation satisfies φ(L j , α). ✷

In order to use state-of-the-art maxsat solvers to compute α-proportion-approval co-winners, we can easily transform

V into a set of clauses of quadratic size: given some LP-tree L j , we introduce a new propositional variable L j , and define a set of clauses j in which every clause has the form C ∨ ¬L j , so that an interpretation can satisfy L j and all the clauses in j only if it satisfies all the constraints encoded in j . The definition of j is recursive, based on the formula φ(L j , α),

of the form l i 1 ⋄ 1 (l i 2 ⋄ 2 (. . . (l i M-1 ⋄ M-1 l i M ) . . .)): • j is initialized to {l i M ∨ ¬L j }; • at the next stage, if ⋄ M-1 is a conjunction, then j becomes {l i M-1 ∨ ¬L j , l i M ∨ ¬L j }; if ⋄ M-1 is a disjunction, then j becomes {l i M-1 ∨ l i M ∨ ¬L j }; • more generally, at the (M -k)th stage, if ⋄ i k is a conjunction, then we add l i k ∨ ¬L j to j ; otherwise, when ⋄ i k is a disjunction, then we add l i k as new disjunct to every clause in j . Example 5. For L P 1 and α = 3/8, φ(L P 1 , 3/8) = M ∧ (F ∨ ¬P ): the set of clauses is initialized to {¬P ∨ ¬L 1 }; it then becomes {F ∨ ¬P ∨ ¬L 1 }, and finally {M ∨ ¬L 1 , F ∨ ¬P ∨ ¬L 1 }. For α = 5/8, φ(L P 1 , 5/8) = M ∨ (P ∧ F ) thus the set of clauses is initialized to {F ∨ ¬L 1 }, then becomes {P ∨ ¬L 1 , F ∨ ¬L 1 }, and finally {M ∨ P ∨ ¬L 1 , M ∨ F ∨ ¬L 1 }.
For an LP-profile V , we obtain a set of "hard" clauses (V ) = L j ∈V j , and the partial weighted maxsat instance consists in finding valuations that satisfy all clauses in (V ), and a maximum number of the L j 's.

With this translation, the number of hard clauses for each voter is the number of 1's in α, and the size of the largest clause becomes one plus the number of 0's in α. It follows that the size of j for each voter is in O (M 2 ), and the translation, with n voters, is in O (M 2 n); in terms of the parameters used in general to describe maxsat instances, the number of clauses is in O (nM), their size is bounded by M, and the number of variables is q. Given the performances of the best current maxsat solvers, this approach may be applicable when there are hundreds of thousands of voters, for some M ≤ 10.

We conclude this section by a proof that winner for α-proportion approval is NP-hard, which means that we may not expect much better than the above translation. In fact, our proof stems from the reverse translation. We will show that the model of a class of logical formulas can be encoded by α-proportion approval winners. Note that a formula φ(L, α) for some LP-tree L and some α always has the form

l i 1 ⋄ 1 (l i 2 ⋄ 2 (. . . (l i M-1 ⋄ M-1 l i M ) . . .)) (2)
where the l i j 's are literals, each over a different variable, and where each ⋄ i is a connective ∧ or ∨, that only depends on the base 2 representation of α:

let α = (0.α 1 . . . α M ) 2 , then ⋄ i is ∧ if α i = 0, and ⋄ i is ∨ if α i = 1.
For any formula φ that has the form as in (2), we construct an LP-tree L(φ) as follows:

• the importance structure is unconditional: [X i 1 ⊲ X i 2 ⊲ . . . ⊲ X i M-1 ⊲ X i M ⊲ Others],
where X i j is the issue correspond- ing to the literal l i j , and where 'Others' refers to all other issues.

• the local preference for issue X i j is unconditional and is

1 i j ≻ 0 i j if l i j = X i j , or 0 i j ≻ 1 i j if l i j = ¬X i j .
Then, given a set of formulas having a common structure corresponding to some fraction α ∈ Rat(M), α = 1/2, we can define the profile V = {L(φ) | φ ∈ } of LP-trees with unconditional importance and unconditional local preferences: the α-proportion approval co-winners correspond to the valuations that satisfy a maximum number of formulas of . We now prove that generalized maxsat remains NP-complete when restricted to this type of formulas.

Formally, given a set of propositional symbols P and a fraction α = (0.α 1 . . . α M ) 2 ∈ Rat(M), let F (P, α) be the set of formulas of the form as in [START_REF] Lacy | A problem with referenda[END_REF]. We define max(α)sat to be the problem that consists in finding a valuation satisfying a maximum number of formulas of a given set ⊆ F (P, α), for a given set of propositional variables P. In the rest of this section, we take P = I. )sat is max2sat, known to be NP-complete [32]. Consider next the case α = 1/4 = (0.01) 2 : F (P, 1 4 ) is the set of 2-cubes (conjunctions of two literals). Let ⊆ F (P, 1 4 ): then ′ = {¬φ | φ ∈ } is equivalent to a set of 2-clauses, and satisfying as many formulas of as possible amounts to satisfying as few formulas of ′ as possible. So max( 14 )sat is equivalent to min2sat, known to be NP-complete too [START_REF] Kohli | The minimum satisfiability problem[END_REF].

Let α = (0.α 1 . . . α M ) 2 = 1 2 α 1 + 1 4 α 2 + . . . + 1 2 M α M .
Suppose first that α 1 = 0. We give a polynomial reduction from max(2α)sat to max(α)sat. Note that 2α = (α 1 .α 2 . . . α M ) 2 = (0.α 2 . . . α M ) 2 has a base-2 representation of length strictly smaller than that of α. Let ⊆ F (P, 2α), let P ′ = P ∪ {X 0 }, where X 0 is a new variable (not belonging to P), and define

′ = {X 0 ∧ φ | φ ∈ }: then ′ ⊆ F (P ′ , α
). Now, satisfying as many formulas of as possible is equivalent to satisfying as many formulas of ′ as possible, since only positive occurrences of X 0 appear in ′ .

Finally, suppose that α 1 = 1: we will prove that max(2α -1)sat can be reduced to max(α)sat. Note that in this case 2α -1 = (0.α 2 . . . α M ) 2 has a base-2 representation of length strictly smaller than that of α. Let ⊆ F (P, 2α -1), let P ′ = P ∪ {X 0 }, where X 0 is a new variable -not in P, and define

′ = {X 0 ∨ φ, ¬X 0 ∨ φ | φ ∈ } ⊆ F (P ′ , α): ′ is obtained
from by two copies of each φ ∈ , and appending at the beginning a disjunction, one with X 0 and one with ¬X 0 .

Suppose that m is a valuation over P that satisfies µ formulas of : let m ′ be an extension of m with some value for X 0 , then m ′ satisfies | | + µ formulas of ′ . Conversely, if a valuation m ′ over P ′ satisfies λ formulas of ′ , then λ ≥ | | because m ′ must satisfy one of X 0 and ¬X 0 , and the restriction of m ′ to P satisfies λ -| | formulas of . So satisfying as many formulas of as possible is equivalent to satisfying as many formulas of ′ as possible.

A simple induction on the length of the base-2 representation of α then proves the result: the base cases correspond to a length 2 (α = 1/4 or 3/4). ✷ Theorem 6. For any fraction α ∈ Rat(M), α = 1/2, winner for α-proportion-approval is NP-complete, even if all trees have unconditional importance and unconditional local preferences.

Proof. We have seen that α-approval winner is equivalent to max(α)sat, and we have just proved that the latter is NP-hard. The fact that these problems are in NP stems from the fact that generalized maxsat is in NP. ✷

Borda

In this section, we provide a translation of winner determination for the Borda rule into a weighted minsat problem. We also show that computing the Borda winner given an LP-profile is hard, except in the simple case where the preferences and the importance relations are unconditional.

Recall that the Borda score of an alternative d w.r.t. LP-tree L is S Borda (L, d) = mrank(L, d), with m = 2 q and rank(L,

d) = 1 + q i=1 2 q-level(L,d, X i ) (L, d, X i ). Hence, the Borda score of d for profile V = (L 1 , . . . , L n ) is: S Borda (V , d) = n j=1 2 q -1 - q i=1 2 q-level(L j ,d,X i ) (L j , d, X i ) = n j=1 q i=1 2 q-level(L j ,d,X i ) (1 -(L j , d, X i )).
The Borda winner is the alternative d that maximizes this score. As we shall see shortly, this optimization problem is hard in the general case. Let us start with a case in which the winner can be computed in polynomial time.

If the importance structure is unconditional, then level(L j , d, X i ) does not depend on d; let us write it more simply level(L j , X i ). It can be computed in polynomial time by a simple exploration of the tree L j . Similarly, if the local preferences are unconditional, then (L j , d, X i ) does not depend on the whole vector d either but only on d i , thus we write (L j , d i ) = (L j , d, X i ). When, for every voter, the importance structure and the local preferences are unconditional, we can thus write:

S Borda (V , d) = n j=1 q i=1 2 q-level(L j ,X i ) (1 -(L j , d i ))
This means that we can choose in polynomial time the winning value for each issue independently: it is the value d i that maximizes

n j=1 2 q-level( X i ,L j ) (1 -(L j , d i )).
Theorem 7. If, for every voter, the importance structure and the local preferences are unconditional, then winner for Borda can be computed in polynomial time. 3. LP tree L P 1 and its translation into weighted formulas.

M m ≻ m 4 : M F 2 : M ∧ F f ≻ f P 1 : M ∧ ¬P p ≻ p P p ≻ p 2 : ¬M ∧ P F p : f ≻ f p : f ≻ f 1 : ¬M ∧ P ∧ F 1 : ¬M ∧ ¬P ∧ ¬F m m Fig.
As we will see shortly, if we lift either one of the unconditionality conditions, computing the Borda winners becomes NP-hard. However, we first describe how this problem can be converted to a weighted minsat problem.

We consider one propositional variable X i for each issue X i ∈ I. Let L be an LP-tree and t a node of L. Let X i be the issue associated with t, and l be the level of t in L (where level 1 corresponds to the root and level q to the leaves). Let v be the instantiation of Inst(t) in that branch, we can associate with it a conjunction V of literals as follows: for every variable X i in Inst(t), V contains either X i if v has value 1 i for X i , or ¬X i if v has value 0 i for X i . Then for each rule u : x ≻ x ′ in the table associated with X i at t, let U be the similar logical translation of u; we define the formula ψ t,u , with weight 2 q-l for minsat, as follows:

• 2 q-l : U ∧ V ∧ X i if x = 1 i ; and • 2 q-l : U ∧ V ∧ ¬X i if x = 0 i ,
As an example, LP tree L P 1 is recalled on Fig. 3 with the corresponding weighted formulas. Alternative m p f satisfies the formula ¬M ∧ ¬P ∧ ¬F , with weight 1: this alternative will be ranked 8 -1 = 7th; alternative m f p satisfies M and M ∧ ¬P , with weight 4 + 1 = 5, so it is ranked 8 -5 = 3rd. Proposition 8. Let L be an LP tree, let (L) = {ψ t | t node of L}, and let d be an alternative. The sum of the weights of the formulas of (L) that are satisfied by d is the Borda score of d w.r.t. L.

Proof. The formulas that are satisfied by d are all on the branch corresponding to d in L. Considering a node t i on this branch labelled with variable X i , the level of t i is precisely level(L, d, X i ), so the weight is 2 p-level(L,d, X i ) , and the formula is satisfied if and only if the preferred value for X i -given the values of d for the issues above t i in this branch -is the value given by d, so the overall weight is

q i=1 2 p-level(L,d, X i ) (1 -(L, d, X i ))
which is exactly the Borda score of d w.r.t. L. ✷ Given an LP-profile V = (L 1 , . . . , L n ), we consider the multiset of weighted formulas (V ) = ∪ j (L j ) (note that there may be several copies of the same weighted formula) and we look for a valuation maximizing the sum of the weights of the formulas in (V ) that it satisfies. Since the formulas in (V ) are conjunctions of literals, (V ) = {(w : ¬φ) | (w : φ) ∈ (V )} is a set of weighted clauses, and a valuation minimizes the weights of the clauses satisfied in (V ) if and only if it maximizes the sum of the weights of the cubes satisfied in (V ), and this is an instance of weighted minsat.

On our example we get

(L P 1 ) = 4 : ¬M, 2 : ¬M ∨ ¬F , 1 : ¬M ∨ P , 2 : M ∨ ¬P , 1 : M ∨ ¬P ∨ ¬F , 1 : M ∨ P ∨ F Theorem 9.
For any profile V of LP-trees, there is a set of weighted clauses C of size polynomial in the size of V , such that the set of Borda co-winners for V is exactly the set of the valuations of C with the lowest weight. Some minsat solvers use a translation of minsat instances into maxsat ones. Using the same approach, we can also directly translate the winner problem for Borda into a weighted maxsat instance, but with more clauses: each weighted conjunction of literals φ = (w : l 1 ∧ . . . ∧ l k ) that appears in (V ) is translated into a set of k weighted clauses (φ) = {(w : l 1 ), (w : ¬l 1 ∨ l 2 ), . . . , (w : ¬l 1 ∨ ¬l 2 ∨ . . . ∨ l k )}. Let (L) denote the union of the (φ)'s that we get for a tree L. For L P 1 we get:

(L P 1 ) =    4 : M, 2 : M, 2 : ¬M ∨ F , 1 : M, 1 : ¬M ∨ ¬P 2 : ¬M, 2 : M ∨ P , 1 : ¬M, 1 : M ∨ P , 1 : M ∨ ¬P ∨ F 1 : ¬M, 1 : M ∨ ¬P , 1 : M ∨ P ∨ ¬F    L j L ′ j L L ′ X i1 X i2 d i1 X i3 A B X i2 di1 X i3 d i2 A B X i3 di2 A d i3 B B di3 A X i1 X i2 X i3 A B A B A B A : 1 ≻ 0; all other issues: 0 ≻ 1 1 ≻ 0 1 ≻ 0 A, B : 1 ≻ 0
for all issues for all issues Other: 0 ≻ 1 Fig. 4. Reduction of 3sat to evaluation with Borda score and unconditional preferences.

For a profile V , (V ) then denotes the union of the sets of weighted clauses obtained for each voter in V . To see why this maxsat formulation is equivalent to our Borda score maximization problem, consider an alternative d, and a weighted conjunction φ = (w : l 1 ∧ . . . l k ) ∈ (V ):

• if d |= l 1 ∧ . . . l k ,
∨ . . . ∨ ¬l j-1 ∨ l j ).
Therefore, the "score" of d for (V ) is

(w:C)∈ (V ) d| =C w|C | + (w:C)∈ (V ) d | =C w(|C | -1) = (w:C)∈ (V ) w(|C | -1) + (w:C)∈ (V ) d| =C w.
It is therefore a constant independent of d, plus the "score" of d for (V ); thus maximizing the sum of the weights of the satisfied cubes in (V ) is equivalent to maximizing the sum of the weights of the satisfied clauses in (V ). Since (V ) contains at most q clauses of size at most q for each node in an LP-tree in V , its size is in O (q 2 |V |). Whether using a maxsat solver on this translation would be more efficient than using a recent minsat solver on (V ) remains to be tested.

We show next that we cannot expect a much better way of computing the Borda winner in the general case, since the problem is NP-complete.

Theorem 10. evaluation is NP-complete for Borda, even if a single one of the following restrictions holds:

1. the local preferences of all voters are unconditional; or 2. the importance structure is the same for all voters and is unconditional.

Proof. evaluation is in NP, because the Borda score of each alternative can be computed in polynomial time. We prove NP-hardness in the two subcases 1 and 2 by two different reductions from 3sat: in a 3sat instance, we are given a formula F over binary variables X 1 , . . . , X q , which is a conjunction of t 3-clauses, F = C 1 ∧ . . . ∧ C t . We are asked whether there exists a valuation of the variables X 1 , . . . , X q under which F is true.

We will now describe how we can reduce a 3SAT instance to two evaluation instances, one with a profile with unconditional preferences, the other with a profile with common, unconditional importance.

Reduction with unconditional local preferences.

There are q + 2 issues: I = {A, B} ∪ {X 1 , . . . , X q }. We first define the following 2t + 2 LP-trees from which the profile is constructed.

• For each j ≤ t, we define two LP-trees L j and L ′ j with the following structures. Suppose C j contains variables

X i 1 , X i 2 , X i 3 (i 1 < i 2 < i 3 ), and d i 1 , d i 2 , d i 3 are the valuations of X i 1 , X i 2 , X i 3 that correspond to literals in C j : for in- stance, if C j = X 1 ∨ ¬X 3 ∨ X 5 then d i 1 = 1, d i 2 = 0, d i 3 = 1.
In the importance order of L j , the first three issues are X i 1 , X i 2 , X i 3 . The fourth issue is A and the fifth issue is B if and only if

X i 1 = d i 1 , X i 2 = d i 2 , or X i 3 = d i 3 ;
otherwise the fourth issue is B and the fifth issue is A. The other issues are ranked below in a fixed order, independent of j.

The local preferences in L j are 0 ≻ 1 for all issues except A, for which it is 1 ≻ 0. In L ′ j the importance order is

[X i 1 ⊲ X i 2 ⊲ X i 3 ⊲ A ⊲ B ⊲ Others],
and the local preferences are 1 ≻ 0 for all issues. The trees are depicted on the left half of Fig. 4.

X 1 X q A L j 0 ≻ 1 d i1 d i2 d i3 : 1 ≻ 0 if d i1 d i2 d i3 |= C j 0 ≻ 1 otherwise L ′ j 1 ≻ 0 L 0 ≻ 1 1 ≻ 0 L ′ 1 ≻ 0 1 ≻ 0 Fig. 5.
Reduction of 3sat to evaluation with Borda score and common, unconditional importance.

• There are two additional LP-trees L and L ′ with the same importance order [A ⊲ B ⊲ Others]; in L the local preferences are 1 ≻ 0 for all issues; in L ′ the local preferences are 1 ≻ 0 for A and B, and 0 ≻ 1 for all other issues.

Let d = d ′ ab be an alternative, where a ∈ {0, 1} is its value for issue A, b ∈ {0, 1} its value for issue B, and d ′ its projection onto {X 1 , . . . , X q }. Because the preferences concerning each of the X i 's are opposite in L j and L ′ j , the Borda score of d for the profile {L j , L ′ j } is a constant K 1 independent of j and d, plus the score for issues A and B, ranked fourth and fifth out of q + 2 issues. If we let 1 j = 1 if d ′ |= C j , and 1 j = 0 otherwise we have:

S Borda ({L j , L ′ j }, d ) = K 1 + 1 j (a2 q-2 + (1 -b)2 q-3 ) + (1 -1 j )((1 -b)2 q-2 + a2 q-3 ) + a2 q-2 + b2 q-3 = K 1 + 2 q-3 [1 j (2a + 1 -b) + (1 -1 j )(2(1 -b) + a) + 2a + b]
The Borda score of d for profile {L, L ′ } is a constant K 2 plus the score for issues A and B, ranked first and second:

S Borda ({L, L ′ }, d ) = K 2 + 2 × (a2 q+1 + b2 q ) = K 2 + 2 q+1 (2a + b).
We now describe the preference profile. It contains 4t LP-trees:

V = {L j , L ′ j : 1 ≤ j ≤ t} ∪ V ′ , where V ′ is composed of t copies of {L, L ′ }. Let K = K 1 + K 2 , then: S Borda (V , d ) = t K + 2 q-3 j [1 j (2a + 1 -b) + (1 -1 j )(a + 2 -2b)) + 2a + b] + t2 q+1 (2a + b).
In particular, if a = 0 or b = 0, then 2a + 1b + 2a + b ≤ 5 and a + 2 -2b + 2a + b ≤ 5, thus, independently from the value of 1 j , the term in the sum is bounded by 5 for every j; thus S Borda (V , d) ≤ t K + 5t2 q-3 + 2t2 q+1 . Or, equivalently: if S Borda (V , d) > t K + 5t2 q-3 + 2t2 q+1 , then it must be the case that a = b = 1. Now, consider a threshold T = t K + 5t2 q-3 + 3t2 q+1 . Suppose first that d is such that S Borda (V , d) ≥ T > t K + 5t2 q-3 + 2t2 q+1 . Then its values for A and B must both be 1, and

S Borda (V , d ) = t K + 2 q-3 j [2 × 1 j + (1 -1 j ) + 3] + 3t2 q+1 = t K + 2 q-3 j [4 + 1 j ] + 3t2 q+1
. Now, since S Borda (V , d ) ≥ T , it must be the case that 1 j = 1 for every clause C j , thus the projection of d onto D satisfies F ; therefore F is satisfiable.

For the converse, suppose that F is satisfiable: let d ′ be a valuation that satisfies F , and consider the alternative

d ′ 1 A 1 B : S Borda (V , d ′ 1 A 1 B ) = T , where T = t K + 5t2 q-3 + 3t2 q+1 .
Reduction with a common, unconditional importance structure. There are q + 1 issues:

I = {X 1 , . . . , X q } ∪ {A}. Let O = [X 1 ⊲ X 2 ⊲ • • • ⊲ X q ⊲ A]
denote the fixed importance relation for the LP-trees. We construct a profile V consisting of 4t LP-trees with conditional importance relation O, defined as follows:

• For each j ≤ t, V contains two LP-trees L j and L ′ j with unconditional local preferences for every issue except A:

suppose C j contains variables X i 1 , X i 2 , X i 3 (i 1 < i 2 < i 3 ), in both LP-trees, Par( A) = {X i 1 , X i 2 , X i 3 }.
The CPTs are defined as depicted on Fig. 5:

in L j , for every assignment

(d i 1 , d i 2 , d i 3 ) of {X i 1 , X i 2 , X i 3 }, the CPT entry for A is d i 1 d i 2 d i 3 : 1 ≻ 0 if and only if C j is satisfied by (d i 1 , d i 2 , d i 3 )
; the local preference is 0 ≻ 1 for every other issue. -in L ′ j , the CPT for A is the same as in L j , and the local preference is 1 ≻ 0 for every other issue. • V contains 2t additional LP-trees: t copies of L, where the local preference is 1 ≻ 0 for issue A, and 0 ≻ 1 for the other q issues; and t copies of L ′ , where the local preferences are 1 ≻ 0 for all issues.

The additional 2t LP-trees are used to make sure that we only need to focus on alternatives whose A-component is 1.

Let d ′ = (d 1 , . . . , d q ) be a valuation of X 1 , . . . , X q . Then:

• S Borda ({L, L ′ }, d ′ 0 A ) = q i=1 2 q+1-i (1 + 0) = 2(2 q -1)
: there are q + 1 issues, issues X 1 , . . . X q have ranks 1 to q, and whatever the value of d i , it counts for 1 in one of the two trees, 0 in the other; 0 A is not the preferred value in L and L ′ , so it does not add anything to the Borda score of d

′ 0 A . • S Borda ({L, L ′ }, d ′ 1 A ) = 2(2 q -1) + 2, because 1 A is the preferred value for A in L and L ′ . • S Borda ({L j , L ′ j }, d ′ 0 A ) = 2(2 q -1) + 2(1 -1 j ) (where again 1 j = 1 if d ′ |= C j , and 1 j = 0 otherwise). • S Borda ({L j , L ′ j }, d ′ 1 A ) = 2(2 q -1) + 2 × 1 j . Thus S Borda (V , d ′ 0 A ) = 4t(2 q -1) + 2t -2K (F , d ′ ), where K (F , d ′ ) is the number of clauses in F that are satisfied by d ′ ; whereas S Borda (V , d ′ 1 A ) = 4t(2 q -1) + 2t + 2K (F , d ′ ).
Hence there exists an alternative whose Borda score is at least T = 4t(2 q -1) + 4t if and only if the 3sat instance is a yes instance. This completes the proof. ✷

Beyond Borda and k-approval. We end this section by discussing the generalization of the constructions of equivalent satisfiability problems for k-approval and Borda to other scoring rules. The common point of the two constructions is that the set of weights has the nice property that only a small number of formulas was needed to encode the scores obtained by the alternatives: more precisely, the number of formulas generated for a single LP-tree is at most the number of nodes of the LP-trees, and each formula has a size in O (q), thus the total size of the construction is in O (q. n j=1 |L j |), while the number of alternatives (2 q ) can, in general, be exponentially larger.

• In the case of k-approval, this is due to the fact that the number of different weights in the scoring vector is very small (only two).

• In the case of Borda, this is due more generally to the fact that the weights are regular enough so that they can be generated by a succinct basis.

The construction can thus be generalized to scoring vectors that use a small number of weights, or more generally a "small basis". We give an example: s = (s 1 , . . . , s 2 q ) where

s j =    2(2 q-2 -j + 1) if j ≤ 2 q-2 1 if 2 q-2 + 1 ≤ j ≤ 2 q-1 0 if j > 2 q-1
The corresponding set of weighted formulas -assuming for simplicity that L P has an unconditional structure X 1 ⊲ X 2 ⊲ X 3 and local preferences x i ≻ x i for every i -is

{2 q-2 : X 1 ∧ X 2 ∧ X 3 ; 2 q-3 : X 1 ∧ X 2 ∧ X 4 ; . . . , 2 : X 1 ∧ X 2 ∧ X q ; 1 : X 1 ∧ X 2 ; 1 : X 1 }
For instance, for q = 4 we get s = (8, 6, 4, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0) and the set of weighted formulas corresponding to

L P is {4 : X 1 ∧ X 2 ∧ X 3 ; 2 : X 1 ∧ X 2 ∧ X 4 ; . . . , 2 : X 1 ∧ X 2 ∧ X q ; 1 : X 1 ∧ X 2 ; 1 : X 1 }

Condorcet

We first observe that the existence of a Condorcet winner is not guaranteed for LP profiles: Example 6. Consider the following profile with two issues X and Y , and three voters:

1: X ⊲ Y , x ≻ x, y ≻ ȳ: her preference relation is xy ≻ x ȳ ≻ xy ≻ x ȳ. 2: Y ⊲ X, x ≻ x, y ≻ ȳ: her preference relation is xy ≻ xy ≻ x ȳ ≻ x ȳ. 3: Y ⊲ X, x ≻ x, ȳ ≻ y: her preference relation is x ȳ ≻ x ȳ ≻ xy ≻ xy.
It can be checked easily that this profile has no Condorcet winner.

For any type of LP profiles, deciding whether a given alternative c is a Condorcet winner is in coNP: a certificate that c is not a Condorcet winner is an alternative d that beats c, which can be checked by comparing d and c for every LP-tree in the profile.

The following result shows that checking if a given alternative is a Condorcet winner is hard.

Theorem 11. For LP profiles, deciding whether a given alternative is a Condorcet winner is coNP-hard, even if, for every voter, the local preferences are unconditional and the importance tree is unconditional.

Proof. We prove the hardness using a reduction from the decision version of max horn-sat, known to be NP-complete [START_REF] Jaumard | On the complexity of the maximum satisfiability problem for Horn formulas[END_REF] Input a Horn formula F = C 1 ∧ • • • ∧ C t over variables {X 1 , . . . , X q }, and an integer number K .

Question Is there a valuation that satisfies more than K of the t clauses?

Let the set of issues be {c} ∪ {X 1 , . . . , X q }. For a valuation d over {X 1 , . . . , X q } we consider the completions d0 c and d1 c of d, and we define the following LP-trees:

L 0 : the importance order is [c ⊲ Others], and the local preferences are 0 ≻ 1 for all issues. Note that d0 c ≻ L 0 d1 c L 0 1 for all d.

L j , if

C j = ¬X 1 ∨ • • • ∨ ¬X l : the importance order is [X 1 ⊲ • • • ⊲ X l ⊲ c ⊲ Others]
and the local preferences are:

• 0 ≻ 1 for X 1 . . . X l ; • 1 ≻ 0 for the other issues. Note that if d |= C j , then d1 c ≻ L j d0 c ≻ L j 1, and if d |= C j , then 1 L j d1 c ≻ L j d0 c . L j , if C j = ¬X 1 ∨ • • • ∨ ¬X l ∨ X l+1 : the importance order is [X 1 ⊲ • • • ⊲ X l+1 ⊲ c ⊲ Others],
and local preferences 0 ≻ 1 for issues c, X 1 , . . . , X l , and 1 ≻ 0 for other issues; then

• d0 c ≻ L j d1 c ≻ L j 1 if d |= ¬X 1 ∨ • • • ∨ ¬X l ; • d0 c ≻ L j 1 L j d1 c if d |= X 1 ∧ • • • ∧ X l ∧ X l+1 ; • 1 ≻ L j d0 c ≻ L j d1 c if d |= C j (
where the first preference comes from the facts that 1 and d0 c coincide on X 1 , . . . , X l and that 1 l+1 ≻ 0 l+1 ).

Let V be a containing two copies of each L j for 1 ≤ j ≤ t, and 2t -4K copies of L 0 . Let N(d) be the number of clauses satisfied by d. The number of LP-trees in V that rank d0 c ahead of

1 is 2t -4K + 2N(d); since V contains 4t -4K LP-trees, d0 c ≻ V 1 if and only if 2t -4K + 2N(d) > 2t -2K , that is: d0 c ≻ V 1 if and only if N(d) > K (3)
Hence, if there is a valuation d that satisfies more than K clauses, then 1 is not a Condorcet winner because

d0 c ≻ V 1.
Conversely, assume there is an alternative This shows that 1 is not a Condorcet winner if and only if there is a valuation that satisfies more than K clauses, hence the coNP-completeness result. ✷

d ′ that beats 1. If d ′ is of the form d0 c then d ′ satisfies more than K clauses because of equivalence (3) above. If d ′ is of the form d1 c , then 2t -4K + 2N 1 (d) > 2t -2N 1 (d), where N 1 (d)
From this result we infer that deciding the existence of a Condorcet winner for a profile consisting of LP-trees with fixed importance structure is in NP NP = P 2 . Whether it is P 2 -complete is an open problem. This hardness result is likely to extend to the winner problem for most Condorcet-consistent rules, which elect the Concorcet winner whenever there exists one. This is left for further research (see however the conference version of our paper for some preliminary results).

Fixed importance LP-profiles

We now focus on the class of profiles with fixed importance tree (conditional or unconditional), common to all voters: LP-trees given by all voters have a common importance structure but may have different local preferences on the values of issues. Let us refer to such LP profiles as FCI profiles; if the fixed importance structure is unconditional then we say that the profile is FUI. This restriction is practically significant, as in many contexts we may assume that there is an objective relative importance of issues, common to all agents. (This can be compared to the assumption that all agents have common preferential dependency structure between variables, commonly made in voting on combinatorial domains [START_REF] Lang | Voting in combinatorial domains[END_REF].) We may wonder whether this restriction makes winner determination easier for some of the voting rules we consider. The existence of a Condorcet winner for FCI profiles was proven in [START_REF] Xia | Strategy-proof voting rules over multi-issue domains with restricted preferences[END_REF]. We first define below a rule which is specifically tailored for FCI profiles, and then give some tractability results for other rules in this case.

The sequential majority winner and Condorcet-consistent rules

A rule which, for this domain restriction, is easy to compute and cheap in terms of communication, is defined in [START_REF] Lang | Sequential composition of voting rules in multi-issue domains[END_REF]: we choose a value for the issue at the root of the tree according to the majority rule (possibly with a tie-breaking mechanism if we have an even number of voters); then, we go down the branch corresponding to the winner for this issue, and choose a value for the issue at the next node using again the majority rule; and so on. The winner is called a sequential majority winner. When n is odd, there is a unique winning value at each step, and therefore, a unique sequential majority winner. When n is even, all winners obtained by choosing an arbitrary value in case of a tie are called sequential majority cowinners.

It was proven in [START_REF] Xia | Strategy-proof voting rules over multi-issue domains with restricted preferences[END_REF] that for profiles composed of conditionally lexicographic preferences, and with an odd number of voters, the sequential majority winner is a Condorcet winner. This, together with the fact that the sequential majority winner can be computed in polynomial time, shows that the winner of any Condorcet-consistent rule applied to FCI profiles with an odd number of voters can be computed in polynomial time. 3Example 7. Consider the conditional importance tree T I depicted on Fig. 6. Consider a profile V ′ with three voters, all having conditionally lexicographic preferences with the same importance tree T I . To determine the sequential majority winner, we first look at the voters' preferences over the values of the most important issue, namely, M. Assume that two voters prefer m to m: the winning value is m. Now, given that M = m, the second most important issue (for all voters) is F. We look at the voters' preferences over the values of F. Assume that two voters prefer f to f : the winning value is f . Finally, we look at the voters' preferences over the values of P. Assume all voters prefer p to p: the winning value is p, and finally the sequential Condorcet winner is m f p.

k-Approval for FCI profiles

We have seen that computing the winners for α-proportion approval is hard in general for α ∈ Rat(M) \ { 1 2 }, for any positive integer M ≤ q. It turns out that it is easier for FCI profiles, because in this case we can reduce the problem to computing the co-winners for j-approval, with j = α2 M , over a set of partial alternatives that correspond to the paths of length M from the root in the common importance tree T . Formally, this set C(T ) of partial alternatives is defined as follows:

• for every node t of T at level M, labelled with issue X , let C(t) = {x, x}; • if t is a node at a level < M, labelled with issue X , and t has two children, one child t ′ for value x, and another one t ′′ for value x, let

C(t) = {xu | u ∈ C(t ′ )} ∪ {xu | u ∈ C(t ′′ )}; • if t is
a node at a level < M, labelled with issue X , and t has one child t ′ , let

C(t) = {xu, xu | u ∈ C(t ′ )}. • finally, C(T ) = C(root).
For instance, for the tree T 1 depicted on Fig. 6 and for M = 2, C(T 1 ) = {mp, mp, m f , m f }.

The set C(T ) has the following properties:

• every complete alternative extends one and only one partial alternative in C(T ); and for every partial alternative there are 2 q-M complete alternatives that extend it;

• given an LP-tree L with importance tree T , the order ≻ L induces a ranking ≻ M L of the partial alternatives in C(T ): let u, u ′ be two different partial alternatives of C(T ), let d, d ′ be two complete alternatives that extend u and u ′ respectively, then u ≻ M L u ′ if d ≻ L d ′ ; • a partial alternative u is among the best j in C(T ) w.r.t. ≻ M L if and only if every complete alternative d that extends u is among the j2 q-M = α2 q best alternatives of ≻ L . This means that the α2 q best alternatives for ≻ L are entirely defined by the best α2 M partial alternatives in C(T ) w.r.t.

≻ M

L . Therefore: Theorem 12. Let M ≤ q, let α ∈ Rat(M), and let j = α2 M . For FCI profiles, winner for α-proportion approval can be computed in time O ( jnM).

Proof. The procedure proposed at the beginning of section 4 works here too: for all of the n LP-trees in the profile, compute their j best partial alternatives, and compute the j-approval scores of these. ✷ For instance, for the importance tree of Fig. 6, let M = 2 and α = 3/4: each voter will add 1 to the scores of three of the four partial alternatives mp, mp, m f and m f , and the partial winner will be the one with the highest score. The 3/4-proportion-approval co-winners will be the two alternatives that extend that partial winner. This is efficient only if M is a constant: in this case, the running time is linear (in n).

Borda for FCI profiles

We already know, from Theorem 7, that for profiles with unconditional preferences and unconditional importance, the Borda winner can be computed in polynomial time. However, in the case of a common, unconditional importance tree and unconditional preferences, we have moreover an interesting characterization of the Borda (co)winner(s): Theorem 13. For FCI profiles with unconditional importance and unconditional preferences: when n is odd, the Borda winner is the sequential majority winner, and when n is even, the Borda cowinners are the sequential majority cowinners.

Proof. Without loss of generality, assume that the common, unconditional importance order is X 1 ⊲ X 2 ⊲ . . . ⊲ X q . Consider profile V = (L 1 , . . . , L n ) where all the L j 's have that importance order. Let x = x 1 . . . x q denote a sequential majority cowinner. For every i ∈ 1, .., q, let k i be the number of voters with local preference x i ≻ x i : because x is a sequential majority cowinner, we have k i ≥ n 2 ; and the Borda score of x for V can be expressed as S Borda (x) = q i=1 2 q-i k i . Moreover, for any other alternative y = y 1 . . . y q , for every issue X i , let k ′ i be the number of voters who prefer y i over y i : either

y i = x i and k i -k ′ i = 0, or y i = x i and k ′ i = n -k i ≤ n 2 because k i ≥ n 2 , thus k i -k ′ i ≥ 0. Since S Borda (y) = q i=1 2 q-i k ′ i , we have S Borda (x) -S Borda (y) = q i=1 2 q-i (k i -k ′ i ) ≥ 0
and the difference can only be equal to 0 if k ik ′ i = 0 for every issue, that is, if y too is a sequential cowinner.

When n is odd, there is a unique sequential majority winner x, and for every other alternative y there is at least one issue X i such that y i = x i , and then k ′ i = nk i < n 2 ; thus S Borda (x) > S Borda (y). Therefore, in this case, x is the unique Borda winner. ✷ This result is specific to LP-trees with fixed unconditional importance and unconditional preferences. Here is a counterexample for fixed unconditional importance and conditional preferences (note that we already know that in this case, the problem is NP-hard, and therefore we already knew that the Borda winner cannot always be the sequential majority winner). Example 8. Consider three issues, common importance order X 1 ⊲ X 2 ⊲ X 3 , and five LP-trees:

• L P 1 , L P 2 , L P 3 with unconditional preferences x 1 ≻ x 1 , x 2 ≻ x 2 , x 3 ≻ x 3 ; • L P 4 , L P 5 : x 1 ≻ x 1 , x 1 : x 2 ≻ x 2 , x 1 : x 3 ≻ x 3 , x 1 : x 2 ≻ x 2 , x 1 : x 3 ≻ x 3 .
The sequential majority winner is x 1 x 2 x 3 . It is ranked first in the first three votes and last in the last two, therefore its Borda score is 21. The Borda score of x 1 x 2 x 3 (ranked 5th in the first three votes and first in the last two) is 23.

Here is now a counterexample for fixed conditional importance and unconditional preferences. The sequential majority winner is mp f . Its Borda score is 79 (it is ranked first by the voters of the first group and 7th by those of the second group); however, the Borda winner is mp f , with Borda score 84 (it is ranked 5th by voters of the first group and 2nd by those of the second group).

Although, in the case of fixed conditional importance and unconditional preferences, the Borda winner is not always the sequential majority winner, still, it can be computed in time polynomial in the number of nodes of the importance tree, with a bottom-up algorithm that collects the optimal value for each issue in each branch with its contribution to the Borda score, and then chooses, at each binary node, the best value depending on the optimal contributions found in the two branches below it. Before giving the algorithm, we illustrate the method on an example.

Example 10. We consider the same profile as in Example 9. We start with the m branch: outcomes in this branch are of the form mxy, where x is the value for F and y is the value for P. The Borda score of mxy is of the form 4α + 2β + γ , where α (respectively β, γ ) is the number of voters whose preferred value is m for issue M (respectively, x for F and y for P). We can look for the values for F and P that maximize β and γ : starting at the leaf, there are 10 voters who prefer p, 9 who prefer p, so we choose y = p, and get a local score of 1 × 10 = 10. Going up at the F node, all voters prefer f , so we choose x = f , and get a local score of 2 × 19, that we add to what has been scored at the leaf to get a current score of 38 + 10 = 48: this is the best score that we can have for outcomes of the form mxy, and it is reached for m f p. Similarly, outcomes of the form mxy have a score of the form 4α + 2γ + β. We maximize again β and γ by choosing values f and p respectively, and get 2 × 10 + 1 × 19 = 39 as optimal 'subscore' in the m branch: this is the highest we can get for outcomes of the form mxy, and is reached for mf p. Finally, the Borda score of m f p is 4 × 9 + 48 = 84, whereas that of mf p is 4 × 10 + 39 = 79, so the winner is m f p.

We now describe the algorithm. Consider a profile V with common importance tree T . For any node t at level l of T labelled with issue X , let I t = I \ (Anc(t) ∪ {X}). For each voter L j , the subtree of L j rooted at t is an LP-tree over I t ∪ {X}, and completely orders the valuations of I t ∪ {X} -there are 2 q-l+1 of them. Thus, for each value x of X , and each valuation u of I t , we can define their Borda score, w.r.t. to the profile that is composed of the subtrees rooted at t of the L j 's:

S Borda (t, V , xu) = Y ∈I t ∪{X} 2 q-level(t,u,Y ) q j=1 (1 -(L j , u, Y ))
where • level(t, u, Y ) denotes the level of variable Y in the branch of T going through t and continuing according to u; and • (L j u, Y ) denotes the rank, in the local preference of voter j, of the value for Y in u.

If we let t ′

x denote the node below t in the branch corresponding to the value x for X at t, then:

S Borda (t, V , xu) = 2 t-l q j=1 (1 -(L j , xu, X)) + S Borda (t ′ x , V , u)
This shows that, when looking for the partial valuation xu that maximizes this score, we can, for every value x for X , look for the partial valuation u x of I t that maximizes S Borda (t ′ x , V , u x ), and then look for the x that maximizes S Borda (t, V , xu x ).

Algorithm 2 implements this approach.

Algorithm 2: Borda + (t, V ).

input: an importance tree T over a set I of q issues, a node t at level l of T , labelled with X ; a FCI-UP profile V with n voters; output: a pair consisting of a partial valuation of I t that maximizes the partial score at t, and of this optimal partial score;

1. k x ← number of voters in V who prefer x to x; k x ← n -k x ; s x ← 2 q-l k x ; s x ← 2 q-l k x ; 2. if t has a single child t ′ : (a) (u ′ , s u ′ ) ← Borda + (t ′ , V ); (b) if s x ≥ s x : return (xu ′ , s x + s u ′ ); else: return (xu ′ , s x + s u ′ );
3. else if t has two children t ′ and t ′′ , corresponding to values x and x:

(a) (u ′ , s u ′ ) ← Borda + (t ′ , V ); (u ′′ , s u ′′ ) ← Borda + (t ′′ , V ); (b) if s u ′ + s x ≥ s u ′′ + s x : return (xu ′ , s u ′ + s x ); else: return (xu ′′ , s u ′′ + s x ); 4. else (t is a leaf) if s x ≥ s x : return (x, s x ); else: return (x, s x );
Theorem 14. For fixed, unconditional importance (FUI) profiles with unconditional preferences, the Borda winner can be computed in time in O (nN), where N is the number of nodes of the importance tree.

Proof. Algorithm 2 computes a winner with its score. It is called once at each node of the tree, and at each node it must count the number of times each value of the labelling issue is preferred in the profile. ✷

Fixed preferences

We study now the case where all agents have the same local, unconditional preferences. We can assume, without loss of generality that 1 i ≻ 0 i for every agent and every issue X i : issues can be seen as objects, and every agent has a preference for having an object rather than not, everything else being equal. For instance, if a voter has the unconditional importance order X 1 ⊲ X 2 ⊲ X 3 then the ordering over alternatives / sets of objects is 123 ≻ 12 ≻ 13 ≻ 1 ≻ 23 ≻ 2 ≻ 3 ≻ ∅ (where a subset S of {1, 2, 3} represents an alternative that takes 1 on X i if and only if i ∈ S. For example, 13 represents 1 1 0 2 1 3 ).

We consider in this section profiles where all preferences are unconditional, of the form 1 i ≻ 0 i ; we call them FP profiles.

Obviously, the best outcome for every agent is 1, and applying any reasonable voting rule (more precisely, any voting rule that satisfies unanimity) will select this alternative. However, winner determination ceases to be trivial if we have a constraint on the set of feasible alternatives. Constraints can take various forms. In a multiwinner voting domain, the usual constraint is that the number of objects to be taken (that is, the number of elected candidates) is fixed to a constant. More general constraints can consist of lower and upper bounds on the cardinality of the number of objects taken, on their cumulated volume, or more generally, arbitrary constraints expressed in a succinct way as in binary aggregation with constraints [START_REF] Grandi | Lifting integrity constraints in binary aggregation[END_REF]. For the sake of simplicity, the only constraint we are considering here is the simplest one: there is a fixed number K of objects that we can take, or equivalently, a fixed number of issues assigned to true. Let us denote by I[K ] the set of all alternatives d with exactly K issues assigned to true (the feasible alternatives). Then we define the following problems, given a voting rule r for which the winner is determined by maximizing a score S:

EXACT-K WINNER DETERMINATION (for r / S):

Input

an FP LP-profile V , an integer K ≤ q Output find an alternative in I[K ] maximizing S(V , •).

EXACT-K EVALUATION (for r / S):

Input

an FP LP-profile V , two integers K and T Question is there an alternative d in I[K ] such that S(V , d) > T ?

Observation 15. If the voters all have the same importance structure, then for any voting rule satisfying unanimity, exact-K winner determination and exact-K evaluation are in P.

This is straightforward from the fact that all voters have the same preferred set of K issues.

Fixed preferences and unconditional importance

An interesting sub-case is when we have unconditional importance for every voter. Let us refer to such LP profiles as UI-FP profiles. Each voter ranks the objects X 1 , . . . , X q according to how important they are for her, and we want to output the 'best' possible combination of objects. Since each voter only has to specify her (importance) ranking of the objects, a profile has the form (⊲ 1 , . . . , ⊲ n ), where ⊲ i is the object ranking by voter i. We might then be tempted to proceed in two steps:

1. use a classical aggregation rule to aggregate the voters' rankings over issues into a collective ranking over issues; 2. select the first K issues in the resulting ranking.

If Step 1 can be done in time polynomial in the number of issues, then this procedure will be tractable. If exact-K winner determination for voting rule r can be done in such a way using aggregation function f , we say that f simulates r.

The question is, are there any interesting pairs (r, f ) such that f simulates r? The next result answers positively for r = Borda.

Theorem 16 (exact-K winner determination for Borda with UI-FP profiles). Let V = (⊲ 1 , . . . , ⊲ n ) be a UI-FP profile and ⊲ V be the ranking of issues obtained by applying the scoring rule F s with s = (2 q-1 , 2 q-2 , . . . , 1). The top K issues in ⊲ V form the alternative

d ∈ I[K ] with maximal Borda score S Borda (V , d): F s simulates Borda. Proof. For d ∈ I[K ], let X i 1 , . . . , X i K be the issues for which d has value 1. Then S Borda (V , d) = K j=1 S Borda (V , X i j ), where S Borda (V , X i j ) = n j=1 2 q-rank(X i ,⊲ j )
is the contribution of issue X i j to the Borda score of an alternative that assigns it to true. In order to find the alternative in I[K ] with maximum Borda score, we only have to find the K issues X i j that maximize S Borda (V , X i j ), and they are the top K issues in ⊲ V . ✷ Example 11. Consider the FI LP-profile with three voters and five issues [START_REF] Airiau | Aggregating dependency graphs into voting agendas in multi-issue elections[END_REF] and, for K = 3, the best feasible alternative is 0 1 1 2 1 3 1 4 0 5 . This result also shows that the Borda rule applied to UI-FP profiles can be seen as a best-K multiwinner scoring rule [START_REF] Faliszewski | Committee scoring rules: axiomatic classification and hierarchy[END_REF]. The Borda rule is not the only rule which, applied to UI-FP profiles, can be seen as a best-K rule. For instance, if q = 2, then the scoring rule associated with scoring function S, applied to UI-FP profiles, corresponds to a best-K voting rule if and only if s has the form (t 1 + t 2 , t 1 , t 2 , 0).

V = (X 1 ⊲ X 4 ⊲ X 2 ⊲ X 3 ⊲ X 5 , X 2 ⊲ X 4 ⊲ X 5 ⊲ X 1 ⊲ X 3 , X 3 ⊲ X 5 ⊲ X 4 ⊲ X 2 ⊲ X 1 ). We have S Borda (V , d, X 1 ) = 16 + 1 + 1 = 18, S Borda (V , d, X 2 ) = 4 + 16 + 2 = 22, S Borda (V , d, X 3 ) = 2 + 2 + 16 = 20, S Borda (V , d, X 4 ) = 8 + 8 + 4 = 20, and S Borda (V , d, X 5 ) = 1 + 4 + 8 = 13, thus X 2 ⊲ V X 3 ∼ V X 4 ⊲ V X 1 ⊲ V X
A much wider family of multiwinner rules, including best-K , but also many others, is known as committee scoring rules [START_REF] Elkind | Properties of multiwinner voting rules[END_REF]. We may wonder whether other such rules in this family can be obtained by applying some scoring rule to UI-FP profiles. The answer is yes. Taking K = 2 as an example, 1 4 -proportion approval, applied to UI-FP profiles, corresponds to the multiwinner rule that elects the pair of items appearing most frequently as the pair of preferred items in the votes. For instance, if the profile is (a

⊲ b ⊲ c ⊲ d, a ⊲ c ⊲ b ⊲ d, b ⊲ c ⊲ a ⊲ d, c ⊲ d ⊲ a ⊲ b, d ⊲ c ⊲ b ⊲ a)
, then the winner is {c, d} since it appears twice as preferred pair of items while all other pairs appear at most once. This rule is known as the perfectionist rule [START_REF] Faliszewski | Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives[END_REF]. This observation can of course be generalised to 1 2 K -proportion approval for any K . Characterising the exact subset of committee scoring rules that can be recovered this way appears to be a more difficult question, which is left for further study.

We show next that exact-K winner determination for UI-FP profiles and for α-proportion-approval is hard. This implies that no simple aggregation rule, applied to the importance ordering of the voters, can simulate α-proportion-approval.

Theorem 17. Let α ∈ Rat(M), α = 1/2. exact-K winner determination for α-proportion-approval with UI-FP profiles is NP-hard.

Proof. The proof is similar to that of Theorem 6, by reductions from some particular generalized maxsat problems. UI-FP profiles correspond to logical formulas of the type F (I, α) containing only positive literals, since the local preferences are always 1 ≻ 0: let F (I, α) + be the set of such formulas. Let constrained max(α) + sat be the following problem: given a set S of formulas in F (I, α) + and an integer K , find a valuation that assigns exactly K variables to true, and satisfies a maximum number of formulas in S. We prove by induction on the length of the base 2 representation of α that this problem is NP-hard for every α ∈ Rat(M), α = 1/2.

The base case corresponding to α = 1/4 is a generalization of the NP-hard problem bounded densest subgraph (given a weighted graph and an integer k, find a subset of at most k vertices that induces a densest subgraph / maximizes the number of "hit" edges, see e.g. [START_REF] Kortsarz | On choosing a dense subgraph[END_REF]). 4 For the sake of completeness, here is a simple reduction from maximum clique: given a graph G = (I, E), the set of formulas S E of F (1/4, I) is defined as {X i ∧ X j | |(i, j) ∈ E}; and G has a clique of size J if and only if there is a valuation of I that assigns J variables to true, and satisfies at least J ( J -1) formulas of S E .

The base case corresponding to α = 3/4, where formulas are of the form X i ∨ X j , is a generalization of the NP-hard max K-vertex cover problem (see e.g. [START_REF] Marx | Parameterized complexity and approximation algorithms[END_REF][START_REF] Croce | Efficient algorithms for the max k-vertex cover problem[END_REF][START_REF] Bonnet | Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems[END_REF] for a proof of NP-hardness and recent approximation algorithms for max K-vertex cover): given a graph G and an integer K , find a set of K vertices that covers (i.e., contains one of the extremities of) a maximum number of edges of G.

For the induction cases, let α = (0.α 1 . . . α M ) 2 . Suppose first that α 1 = 0; then 2α = (0.α 2 . . . α M ) 2 , and let

= {Y i ∨ φ | φ ∈ , 1 ≤ i ≤ N}.
′ is a set of formulas of F (I ′ , α) + . We claim that there is a valuation m of I assigning exactly K variables in I to true and satisfying at least J formulas in if and only if there exists a valuation m ′ of I ′ assigning exactly K variables in I to true and satisfying at least N J formulas in ′ . If K = |I|, this is straightforward. Assume now K < |I|. For a valuation m of I, let |m| be the number of variables of I assigned to true by m.

• Assume there is a valuation m of I such that |m| = K and satisfying at least J formulas in . Then the extension m ′ of m to I ′ evaluating every Y i to 0 satisfies exactly K variables of I ′ , and at least N J formulas of ′ , since for every φ

∈ and i ≤ N, m |= φ implies m ′ |= Y i ∨ φ. • Conversely,
′ is λN + (| | -λ)(K -|m|) ≤ λN + K | | < λN + N since N = 1 + K | |.
Since we assumed that m ′ satisfies at least N J formulas in ′ , we must have N J < N(λ + 1), therefore J ≤ λ: the restriction of m ′ to I satisfies at least J formulas of . ✷ Example 12. There are four items A, B, C , D, and K = 2. There are five UI-FP LP-trees: Proof. We give a reduction from hitting set to the complementary problem. An instance of hitting set consists of a collection of subsets S 1 , . . . , S p of a set S = {1, . . . , s}, and an integer K ; it is a "yes" instance if there exists a subset S ′ ⊆ S, |S ′ | = K , such that S ′ ∩ S i = ∅ holds for all i. With an instance of hitting set we associate the following instance of condorcet winner checking for FP-UI profiles: the set of issues is I = {X 1 , . . . , X s , Y 1 , . . . , Y K }, and the profile V is composed of 2p -1 FP-UI LP-trees:

L P 1 = L P 2 = A ⊲ B ⊲ C ⊲ D, L P 3 = L P 4 = D ⊲ C ⊲ B ⊲ A,
• for i = 1, . . . , p, if S i = {i 1 , . . . , i |S i | } then L P i is defined by the unconditional preference relation X i 1 ⊲ . . . ⊲ X i |S i | ⊲ Y 1 ⊲ . . . ⊲ Y K ⊲ Others; • for i = p + 1, . . . , 2p -1, L P i is defined by the unconditional preference relation Y 1 ⊲ . . . ⊲ Y K ⊲ Others
Suppose there is a hitting set S ′ of cardinality K for S. Then the first p voters prefer {X j , j ∈ S ′ } to {Y 1 , . . . , Y K }, therefore {Y 1 , . . . , Y K } is not a Condorcet winner.

Conversely, suppose {Y 1 , . . . , Y K } is not a Condorcet winner. Then for some C ∈ I[K ], C = {Y 1 , . . . , Y K }, at least p voters of V prefer C to {Y 1 , . . . , Y K }. But the last p -1 voters have {Y 1 , . . . , Y K } as their preferred committee of size K , therefore the other p must prefer C to {Y 1 , . . . , Y K }, which is the case only if C contains some X i j for all i; but then {i j , i = 1, . . . , p} is a hitting set of size ≤ K for S, therefore there is a hitting set of size K for S. ✷

FP profiles with conditional importance

When the importance order can be conditional, even the Borda rule becomes intractable.

Theorem 19. K -evaluation for Borda with FP profiles is NP-hard.

Proof. We prove NP-hardness by a reduction from restricted x3c, defined as follows: given a set C = {C 1 , . . . , C s }, and a family S = {S 1 , • • • , S t } of subsets of C, with |S j | = 3 for all j, and such that each C i ∈ C appears in no more than three S j 's, we ask whether there is a subset S ′ ⊆ S such that each c i ∈ C appears in exactly one S j ∈ S ′ (which implies |S ′ | = s/3); S ′ is called an exact cover of C. restricted x3c is known to be NP-complete ([44]; problem [SP2] in [45]).

Given such an instance of restricted x3c, we now describe how to reduce it to an instance of K -evaluation with FP LP-trees. Let I = S ∪ C ∪ {C}, where C is a fresh issue.

We define first a set of LP-trees where issues in C are more important than issues in S, themselves more important than C . Specifically, we define the importance order

O = [C 1 ⊲ C 2 ⊲ . . . C s ⊲ S 1 ⊲ S 2 ⊲ . . . ⊲ S t ⊲ C ]
and consider these two cyclic permutations:

• M = S 1 → S 2 → • • • → S t → S 1 is a permutation over S; • N = C 1 → C 2 → . . . → C s → C 1 is a permutation over C.
For 1 ≤ j ≤ t and 1 ≤ i ≤ s, let L i, j be the LP-tree with fixed preferences and unconditional importance order N i (M j (O)); it is depicted on the left of Fig. 7. We define the profile

V = {L i, j |1 ≤ j ≤ t, 1 ≤ i ≤ s}.
Next, for every i ≤ s, we define another set of LP-trees, again depicted on Fig. 7, as follows: let S(C i ) be the set of elements of S that cover C i : recall that 1 ≤ |S(C i )| ≤ 3. Let S ′ (C i ) be some subset of S of cardinality 3 that contains S(C i ) (therefore, S ′ (C i ) is obtained by adding 0, 1 or 2 S j 's to S(C i )). Denote by S j 1 (i) , S j 2 (i) , S j 3 (i) the elements of S ′ (C i ), with j 1 (i) > j 2 (i) > j 3 (i). We define the following two importance orderings over I:

• O i = [S j 1 (i) ⊲ S j 2 (i) ⊲ S j 3 (i) ⊲ C i ⊲ C ⊲ C \ {C i } ⊲ S \ {S j 1 (i) , S j 2 (i) , S j 3 (i) }] • O ′ i = [S j 1 (i) ⊲ S j 2 (i) ⊲ S j 3 (i) ⊲ C ⊲ C i ⊲ C \ {C i } ⊲ S \ {S j 1 (i) , S j 2 (i) , S j 3 (i) }]
The only difference between O i and O ′ i is that C i and C are swapped. Let L ′ i be the LP-tree with the importance order O i in all branches except in the branches with S j = 0 for every S j ∈ S(C i ), where the importance order is O ′ i . For 1 ≤ j < t, let L ′ i, j be the LP-tree with unconditional importance order M j (O i ). For 1

≤ i ≤ s, let V i = {L ′ i } ∪ {L ′ i, j | 1 ≤ j < t}.
We define the profile V ′ = ∪ s i=1 V i , which contains s × t trees.

L i, j Now, let sV + V ′ be the profile that contains V ′ and s copies of V . We now analyze the Borda score of alternative d for this profile. Recall that, since all trees have height t + s + 1, if an issue X is at level l in a tree L, and if d( X) = 1, it contribution to S Borda (L, d) will be 2 t+s+1-l . In the sequel, we denote by S Borda (W , d, X) the contribution of issue X to the Borda score of d for some profile W .

L ′ i L ′ i, j N i (C 1 ) N i (C s ) M j (S 1 ) M j (S t ) C S j1 (i) S j2 (i) 1 S j2 (i) 0 S j3 (i) S j3 (i) 1 S j3 (i) 0 C i 1 C other C j 's other S j 's C 0 C i other C j 's other S j 's M j (S j1 (i) ) M j (S j2 (i) ) M j (S j3 (i)) C i C other C j 's M j (other S ′
• Consider first issue S j ∈ S: because of the symmetries, it will appear s times at each level between s + 1 and s + t in the L i j 's; thus

S Borda (V , d, S j ) = d(S j )s(2 t + . . . + 2 1 ) = d(S j )s(2 t+1 -2).
Similarly, in every V i , S j will appear at each level between 1 and 3 and also at each level between s + 5 and t + s + 1;

thus, since there are s V i 's in V ′ :

S Borda (V ′ , d, S j ) = d(S j )s(2 t+s + 2 t+s-1 + 2 t+s-2 + 2 t-4 + 2 t-5 + . . . + 1)

= d(S j )s(7 × 2 t+s-2 + 2 t-3 -1).

= d(S j )s2 t+s+1 7 8

+ 1 2 s+4 - 1 2 t+s+1 .
Therefore:

S Borda (sV + V ′ , d, S j ) = d(S j )s2 t+s+1 1 - 1 8 + 1 2 s+4 + s 2 s - (1 + 2s) 2 t+s+1 < d(S j )s2 t+s+1 (1 -ǫ)
for any ǫ in ]0, 1 8 [ and for large enough values of s.

For issues in C and for C , the contributions in each V i depend on whether at least one S j ∈ S(C i ) has value 1 in d or not; therefore we define 1 i (d) = 0 if S j = 0 for every S j ∈ S(C i ), and 1 i (d) = 1 otherwise.

• Consider now issue C : it appears at level t + s + 1 in every L i j , so

S Borda (V , d, C ) = d(C )st.
Furthermore, C appears at level 5 in each of the s × (t -1) L ′ i j , and at level 5 or 4 in each L i , depending on whether

1 i (d) = 1 or 0; thus S Borda (V ′ , d, C ) = d(C ) s(t -1)2 t+s-4 + s i=1 1 i (d)2 t+s-4 + (1 -1 i (d))2 t+s-3 = d(C )2 t+s-4 st + s i=1 (1 -1 i (d)) .
In particular, S Borda (sV

+ V ′ , d, C ) ≤ d(C ) s t + s(t + 1)2
2 t+s-4 < S Borda (sV + V ′ , d, S j ) for any S j ∈ S such that d(S j ) = 1 and for large values of t and s.

• Finally, consider issue C i ∈ C: C i will appear t times at each level between 1 and s in the L i j 's; thus

S Borda (V , d, C i ) = d(C i )t(2 t+s + . . . + 2 t+1 ) = d(C i )t2 t+1 (2 s -1).
C i is at level 4 or 5 in L i , depending on whether 1 i (d) = 1 or 0; and at level 4 in each of the t -1 L ′ i j ; it also appears t times at some level between 6 and s + 4 in every 1 8 [ and for large values of t and s.

V i ′ when i ′ = i. Thus S Borda (V ′ , d, C i ) = d(C i ) (1 i (d) + t -1)2 t+s-3 + (1 -1 i (d))2 t+s-4 + t s i ′ =1 i ′ =i 2 t+s+1-level(L ′ i ′ ,C i ) where level(L ′ i ′ , C i ) denotes the level of issue C i in i ′ ; it is independent of d when i ′ = i. In particular, S Borda (sV + V ′ , d, C i ) > S Borda (sV , d, C i ) = d(C i )st2 t+s+1 (1 -1 2 s ) > d(C i )st2 t+s+1 (1 -ǫ) for any fixed ǫ ∈ ]0,
From this analysis, we can see that for any C i ∈ C, S j ∈ S, for large values of t and s, we have that S Borda (sV d,C ). Hence, if we fix K = s + t/3, and look for alternatives d that have no more than K issues equal to 1, and that maximize S Borda (sV + V ′ , d), then such a d will have value 1 for all of the s issues in C, and value 1 for a third of the t issues in S; it will have value 0 for all remaining issues in S and for C . Moreover, its Borda score for sV ′ + V will be:

+ V ′ , d, C i ) > S Borda (sV + V ′ , d, S j ) > S Borda (sV + V ′ ,
S Borda (sV ′ + V , d) = st 3 2 t+s+1 1 - 1 8 + 1 2 s-4 + s 2 s - (1 + 2s) 2 t+s+1 + st2 t+1 (2 s -1) + 2 t+s-4 2t -1 + s i=1 1 i (d) + t s i=1 s i ′ =1 i ′ =i 2 t+s+1-level(L ′ i ′ ,C i )
Now, suppose that the instance of restricted x3c has an exact cover: then it is possible to define d with value 1 for all C i 's, value 1 for 1/3rd of the S j 's -those that are necessary to cover C, and 0 for all the other issues. Because the selected S j 's form an exact cover of C, s i=1 1 i (d) = s, and no alternative with only K issues with value 1 can have a higher Borda score. Let S max Borda (sV ′ + V ) denote this Borda score: if there exists an exact cover for the restricted x3c instance, then there is an alternative with no more than K issues with value 1 and whose Borda score is at least S max Borda (sV ′ + V ). For the converse, suppose that an alternative d has no more than K issues with value 1 and is such that S Borda (sV ′ + V , d) ≥ S max Borda (sV ′ + V ).

Then there must be an alternative d ′ with a score at least as high and where all C i 's have value 1, and 1/3rd of the S j 's have value 1, and all other issues have value 0. But then, it must be the case that s i=1 1 i (d ′ ) = s: we have found an exact cover of C. ✷

Discussion

Committee elections

Committee elections are a major application field of our work, which we have only hinted on in Section 8. Here we discuss in more detail how our work can be applied to this field.

A committee (or multiwinner) voting rule maps a profile into a set of winners, usually of fixed size (corresponding to the number of seats to be filled in the committee). There are two major trends in multiwinner elections; we discuss below the applicability of our setting to each of both. In the first trend, profiles consist of approval ballots: each voter approves a subset of candidates, of arbitrary size (see [START_REF] Kilgour | Approval balloting for multi-winner elections[END_REF] for a survey of a number of such rules and [START_REF] Aziz | Justified representation in approval-based committee voting[END_REF] for a very recent reference). In the second trend, profiles consist of rankings over candidates (see [START_REF] Elkind | Properties of multiwinner voting rules[END_REF] for a very recent reference). In both cases, preferences are unconditional: voters are not allowed to approve or disapprove a candidate conditionally on some other set of candidates being elected or not. A possible generalization of both approval-based and ranking-based multiwinner elections consists in having voters express LP-trees for which (binary) variables correspond to candidates. For instance, the profile of Example 1 could be reinterpreted this way: M (respectively F, P) now means that Mary (respectively Francis, Patricia) is elected; L P 1 now means that the most important for voter 1 is that Mary is elected (maybe because voter 1 is Mary herself!); if she is, then the second most important thing is that Francis is elected too, and if not, that Patricia is elected, and so on. Also, what is most important to voter 2 is that Patricia is not elected.

Although any of the different assumptions corresponding to the different sections of our paper are applicable to multiwinner elections, we feel that the one that applies most directly is Section 8, where voters cannot express negative preferences for a candidate. Expressing LP-trees in this case is a generalization of expressing rankings over candidates, as a ranking is just a UI-FP LP-tree. In Section 8 we have seen that some well-known multiwinner rules can be captured as voting rules on lexicographic preferences, such as some K -best rules and perfectionist rules, all belonging to the family of committee scoring rules [START_REF] Elkind | Properties of multiwinner voting rules[END_REF]. Now, allowing for FP-CI LP-trees leads to a generalized form of ranking-based multiwinner elections, where the ranking over candidates is conditional.

Can approval-based multiwinner rules be captured in our framework? Not as such, because we would have to be able to allow LP-trees with indifferences. In such an extension, not only approval ballots are expressible (with all variables being equally important), but a voter could also express conditional or unconditional (dis)approvals. Note however that in order to be adapted to conditional approval balloting, the general model of aggregating LP-trees needs to be enriched by a cardinality constraint such as we did in Section 8.

How restrictive are conditionally lexicographic preferences?

When the set of alternatives is combinatorial, the number of alternatives is exponential, therefore the number of possible rankings of alternatives is doubly exponential. This leads to this classical tension between expressivity and communication complexity (see for instance the introductory section of [START_REF] Lang | Voting in combinatorial domains[END_REF]): if we don't make any restriction on expressible preferences, then we must accept an exponential communication complexity which makes the mechanism infeasible in practice; and if we do accept a domain restriction, then only an exponentially small proportion of all preference relations will be expressible. The question is to find a domain restriction that is meaningful enough in some classes of situations. Each domain restriction comes with some way of expressing preferences in a succinct way. The most common such languages, with their associated domain restrictions, are the following:

1. each voter specifies a ranking over the domain of each variable, independently of other variables (separable preferences), or a weight function mapping every value of each variable to a number, the weight of a tuple of values then being the sum of the weights obtained for each variable (additively separable preferences). 2. each voter specifies a ranking over single issues.

each voter specifies only her best tuple of values.

For each such way of expressing preferences, the preference relation over the whole domain is then determined using a preference extension principle. Interestingly, LP-trees are a combination of 1 and 2: 1 for the local preferences and 2 for the importance relation. As far as we know, this is the first time 1 and 2 are combined in the setting of preference aggregation over combinatorial domains.

Moreover, the different families of LP-trees offer a wide span of ways of trading off expressivity and communication complexity. If expressivity matters before all, then unrestricted LP-trees allow for considering nonseparable preferences, via the expression of conditional preferences, and a (possibly conditional) importance relation between variables. 6 Note that 1, 2 and 3 are all restricted to separable preferences, and thus disallow the expression of preferential dependencies between variables, which is a huge drawback. Very few methods exist for aggregating preferences over combinatorial domains with preferential dependencies. Among the most prominent ones we find, on the one hand, sequential voting, and on the other hand, voting with conditional preference networks (CP-nets) -see [START_REF] Lang | Voting in combinatorial domains[END_REF] for a review. But sequential voting, among other drawbacks, needs voters to interact again and again with the system, while direct, one-shot methods suffer from the fact that the preference relation induced from a CP-net is generally a partial order, which makes it sometimes impossible to apply a known voting rule (which needs a collection of complete orders). Admittedly, some voting rules can be naturally extended to partial orders, and more precisely to partial order obtained from CP-nets (see [START_REF] Conitzer | Hypercubewise preference aggregation in multi-issue domains[END_REF] for extensions of Copeland, maximin and Kemeny for such profiles); but this is not true for most positional scoring rules such as Borda or k-approval (which are the focus of our paper), for which no extension to partial orders is commonly agreed to be natural. Thus, aggregating LP-trees is, as far as we know, the first direct aggregation method ever that allows nonseparable preferences and makes it possible to apply any classical voting rule.

Of course, expressivity comes with high communication cost: in the worst case, the size of an LP-tree is exponential in the number of variables. Note however that this happens only in the worst case: if voters have few dependencies for their preference and importance relations, then the size of their LP-trees will remain small. This may still be a problem, because in some contexts, the amount of communication between the voters and the voting centre must be very small (as voters are unlikely to be willing to report their preferences if this takes them too long), and then moving to a further restriction might prove useful: with unconditional importance and unconditional preference (UI-UP), an LP-tree needs only polynomial space to be expressed and the communication complexity of aggregating LP-trees becomes polynomial. For the exact communication complexity of expressing various classes of LP-trees see [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF].

One possible way of quantifying how drastic a domain restriction is, consists in counting the number of preference relations that are expressible. This, of course, does not mean that expressing more preferences means being more plausible. 7 Moreover, this way of quantifying a domain restriction may look controversial: if it is too restrictive, it is not a good restriction because too few preference relations can be expressed, but if it is not restrictive enough, then it is not good either because it induces a high communication complexity. Thus, in a sense, a reasonable domain restriction (at least for our purposes) should be neither too expressive nor too restrictive -and of course, it should also be cognitively reasonable. Now, even in the highly restricted cases such as those considered in Sections 7 and 8, the number of expressible LP-trees is still larger than with the classical ways of expressing preferences in combinatorial domains reported in the above list, but exponentially smaller than the number of all preference relations. With fixed importance, there is still a doubly exponential number of expressible LP-trees due to the expression of conditional preferences, and with fixed preferences there is again a doubly exponential number of expressible LP-trees due to the expression of conditional importance. In contrast, with 1, 2 or 3 there is only a simply exponential number of expressible preferences. And furthermore, as said in the Introduction, the lexicographicity assumption, even in its most restricted forms, makes sense from a cognitive point of view.

Nonbinary domains

Although we restricted our study to the case of binary issues for the sake of clarity, let us briefly explain now why most results still hold if we allow non-binary issues. Note first that formula [START_REF] Brams | The paradox of multiple elections[END_REF], that gives the rank of an alternative w.r.t. a given tree, can be generalized to non-binary domains, using products of the sizes of the domains D i : given an alternative d and an LP-tree L, if t i is the node labelled with issue X i in the branch of L corresponding to d, then

• the local rank of the value of d for issue X i in the local preference at t i , still denoted (L, d, X i ), is now a value between 0 (if d i is the preferred value for X i at node t i , given the values of d for the issues that appear above t i ) and |D i | -1 (if d i is the least preferred value for X i at t i );

• moreover, if we denote by X i ⊲ L,d X j the fact that X i is above X j in the branch of L corresponding to d, then the number of alternatives that correspond to the leaves of L below t i and to the left of d is (L, d, X i ) × X i ⊲ L,d X j |D j |

(with the convention that, the empty product, when X i is at a leaf, equals 1).

Thus

rank(L, d) = 1 + q i=1 (L, d, X i ) × X i ⊲ L,d X j |D j |
Therefore, computing, for a given LP-tree, the rank of a given alternative, or the alternative that has a given rank, can both be done, without significant increase in complexity, through a top-down traversal of the tree guided by the given alternative or the given rank. In a similar way, it is still possible to compute in polynomial time the Borda winner when importance and local preferences are both unconditional (Theorem 7), and to design a translation of winner determination into a weighted minsat instance -using weights that are not powers of 2 but that must again be computed through a traversal of each tree; to each issue with d values now correspond d propositional variables, and a polynomial number of "hard" clauses are added to enforce that only one of them can be true. Consider for instance the tree L P 1 , and assume that issue P now has three values p, p ′ and p ′′ . Let L P ′ 1 be the LP-tree identical to L P 1 except that the values for P are ordered p ≻ p ′ ≻ p ′′ in the left branch, and p ′ ≻ p ≻ p ′′ in the right branch; it is depicted on Fig. 8. Then the formula corresponding to the root of L P 1 is still M, but now with a weight of 2 × 3 = 6; then, at the F node down the m branch, the formula is still M ∧ F but with weight 3; there are now two formulas at the leaf of the m branch: M ∧ P with weight 2, and M ∧ P ′ with weight 1; alternative mf p ′ now satisfies M, M ∧ F and M ∧ P ′ and has a Borda score of 10 (mf p ′ is indeed the second best alternative for L P 1 .

The α-proportion approval rule can still be defined, and the translation of winner determination for this rule into a generalized maxsat instance can still be defined. For instance, if α = 0.8, then assuming that we want the ⌊α × 12⌋ = 9 = (1/2 + 1/6 + 1/12) × 12 best alternatives, φ(L P ′ 1 , α) = M ∨ (P ′ ∨ (P ∧ F )). Similarly, if α ′ = 0.45, then assuming that we want the ⌊α ′ × 12⌋ = 5 = (0/2 + 1/4 + 2/12) × 12 best alternatives, φ(L P ′ 1 , α) = M ∧ (F ∨ (P ∨ P ′ )). (Again there is one propositional variable for every value in the domain of every non-binary issue and hard clauses enforce that only one of 7 An example suggested by a reviewer: single-peakedness with respect to a fixed axis is certainly more plausible than the weird domain restriction obtained by fixing the best and the worst alternatives, although the latter can express more preference relations. believe that continuing studying preference representation and aggregation on combinatorial domains, taking advantages of developments in efficient satisfiability techniques, is a promising future work direction.

Although the terminology we used in the paper, as well as the choice of our examples, referred to preference aggregation, our approach can also be relevant to epistemic social choice, where the goal is no longer to aggregate preferences but to search for the most plausible state of affairs by aggregating plausibility orders. Here, the lexicographicity assumption makes sense when an agent considers a state of the world s more plausible than another one s ′ when s has a value considered more plausible than s ′ for her most important variable for which s and s ′ take different values.

  is, an alternative is identified by its values on all issues. Alternatives are denoted by d, e, etc. For any Y ⊆ I we denote D Y = X i ∈Y D i . An element of D Y is called a partial alternative. Let L(D) denote the set of all linear orders over D.

Lemma 5 .

 5 For any α ∈ Rat(M) \ {1/2}, max(α)sat is NP-hard. Proof. By induction. The base cases are α = 3/4 and α = 1/4. Consider first α = 3/4 = (0.11) 2 : F (P, 3 4 ) is the set of 2-clauses (disjunctions of two literals). So max( 3 4

  is the number of clauses in which d satisfies at least one negative literal: then 4N 1 (d) > 4K , i.e., N 1 (d) > K , and since N(d) ≥ N 1 (d), again d satisfies more than K clauses.

Fig. 6 .

 6 Fig. 6. The importance tree T 1 for Example 7.

Example 9 .

 9 Consider the conditional importance tree of Example 7, with three issues M, P and F. We have 19 voters, all preferring f to f , and• for 10 of them we have m ≻ m and p ≻ p;• for the other 9 we have m ≻ m and p ≻ p.

⊆F

  (I, 2α) + . Let I ′ = I ∪ {X 0 }, where X 0 is a fresh variable, and let ′ = {X 0 ∧ φ | φ ∈ }. ′ is a set of formulas of F (I ′ , α) + ; and one can satisfy J formulas of assigning exactly K variables to true if and only if one can satisfy J formulas of ′ assigning exactly K + 1 variables to true. Now, suppose that α 1 = 1. Let α ′ = 2α -1 = (0.α 2 . . . α M-1 α M ) 2 and let ⊆ F (I, 2α -1) + . We introduce N = 1 + K | | fresh variables Y 1 , . . . , Y N , and define I ′ = I ∪ {Y 1 , . . . , Y N } and ′

  assume there is a valuation m ′ of I ′ such that the number of variables of I ′ satisfied by m ′ is K and satisfying at least N J formulas in ′ . Let m be the restriction of m ′ to I, and let λ be the number of formulas in satisfied by m. Note that, since m and m ′ satisfy |m| variables in I, the number ofY i 's satisfied by m ′ is K -|m|. Consider a formula φ ∈ : if m |= φ, then m ′ satisfies the N formulas of the form Y i ∨ φ in ′ ; and if m |= φ, then m ′ still satisfies (K -|m|) formulas Y i ∨ φ.Therefore, since m satisfies λ formulas of , and falsifies | |λ of them, the number of formulas of ′ satisfied by m

Proposition 18 .

 18 and L P 5 = B ⊲ C ⊲ D ⊲ A. The majority relation is B ⊲ C ⊲ D ⊲ A and its dominating two elements are B and C . However, {A, D} majority-dominates {B, C }. Given an FP-UI profile V , an integer K and an alternative d ∈ I[K ], checking whether d is a Condorcet winner is coNP-complete.

Fig. 7 .

 7 Fig. 7. Reduction of restricted x3c to K -evaluation for Borda with fixed preferences.

  2.A conditional preference table CPT(t) for each node t, which is defined as follows. Let Anc(t) denote the set of issues labelling the ancestors of t.

Let Inst(t) (respectively, NonInst(t)) denote the set of issues in Anc(t) that have two (respectively, one) outgoing edge(s). There is a set Par(t) ⊆ NonInst(t) such that CPT(t) is composed of the agent's local preferences over D Iss(t) for all valuations of Par(t). That is, if Iss(t) = X i then for every valuation u of Par(t), the CPT contains either u :

  then d satisfies all clauses in (φ); and • if d |= l 1 ∧ . . . l k , then there is exactly one clause in (φ) that is not satisfied by d (if j is the smallest index such that d |= l j , then d satisfies all clauses in (φ) except ¬l 1

The 2016 maxsat Evaluation webpage is at the address http://www.maxsat .udl .cat /16 /index .html, with links to result tables and benchmarks.

This result extends to profiles with an even number of voters, provided that the rule outputs all weak Condorcet winners when there exists at least one; in this case, the sequential majority cowinners are the weak Condorcet winners.

Even more expressivity can be obtained by considering, as[START_REF] Bräuning | Learning conditional lexicographic preference trees[END_REF], a generalization of LP-trees were a node can contain several variables, deemed to have comparable importance; the extension of our algorithms to such extended LP-trees is left for further research. Note that, as suggested by a reviewer, it is possible to define a measure of how close a preference order is to be captured by efficient LP-trees: a single node can represent anything in space exponential in the number of issues; then the preference order can be decomposed by adding nodes; the "LP-tree-width" can then be the number of issues in the largest node.

, the problem is in P in all cases (Theorem

3).[START_REF] Fraser | Ordinal preference representations[END_REF] They also proved a hardness result for a variant of k-approval.

Acknowledgements

We thank all anonymous reviewers of AAAI-12, CP-12, COMSOC-12 and the Artificial Intelligence journal for their helpful comments and suggestions. This work has been partly supported by the ANR project CoCoRICo-CoDec. Lirong Xia acknowledges supports from NSF under Grant #1136996 to the Computing Research Association for the CIFellows Project, NSF under Grant #1453542 and #1716333, and ONR #N00014-17-1-2621.

Fig. 8. LP tree L P ′ 1 and its translation into weighted formulas.

them is true.) Note that the length of the decomposition of α depends on the order of the non-binary variables in the branches, so that the approach of Theorem 12 in the FCI case cannot work in this more general setting. Finally, membership in NP of the problems we have studied here is not compromised when we consider non-binary issues, and hardness results obviously still hold.

Summary and future work

We first give three tables summarizing the results obtained for Borda, α-proportion approval, and checking whether an alternative is a Condorcet winner. In these tables, "CP" stands for "Conditional Preferences" (no restriction on the preference tables), "UP" means "Unconditional Preferences", whereas "FP" is an abbreviation for "Fixed Preferences": it is assumed that all voters prefer value 1 to 0 for every issue, and we studied the "constrained" case, where there is a bound on the number of issues that can have value 1. Similarly, "CI" and "UI" respectively stand for "Conditional Importance" (no restriction on the tree structure) and "Unconditional Importance" (all trees in the profile are linear). Finally, "FCI" and "FUI" indicate the restriction whereby all voters in the profile have the same tree structure. Our conclusions are partly positive, partly negative. On the one hand, there are voting rules for which the restriction to conditionally lexicographic preferences brings significant simplifications: this is the case, at least, for k-approval for some values of k. The Borda rule can be applied easily provided that both the importance relation and the local preferences are unconditional, which is a very strong restriction. The hardness of checking whether an alternative is a Condorcet winner suggests that Condorcet-consistent rules will be hard to apply as well, which is why we did not focus on them in more detail.

However, we have shown that some of these problems can be reduced to a compact maxsat problem. From a practical point of view, it is important to test the performance of maxsat solvers on these problems. Liu and Truszczi ński [START_REF] Liu | Aggregating conditionally lexicographic preferences using answer set programming solvers[END_REF] have proposed translations of winner determination and evaluation problems for the Borda and k-approval rules into Answer Set Programming, another general paradigm for solving hard combinatorial optimization problems. They showed that winners can be determined in a few minutes for these rules with 10 issues and 1000 voters, or 15 issues and 500 voters. 9 We