Arianna Novaro

Umberto Grandi

Dominique Longin

Emiliano Lorini

Goal-Based Collective Decisions: Axiomatics and Computational Complexity

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Social choice and voting have become part of the standard computational toolbox for the design of rational agents that need to act in situations of collective choice [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF][START_REF] Brandt | Handbook of Computational Social Choice[END_REF]. In a variety of applications ranging from product configuration to multiple sensor control, the space of alternatives from which a collective choice needs to be taken is often combinatorial. This has brought many researchers to introduce compact languages for preference representation, and to design collective procedures that act directly on a compactly represented preference input (see, e.g., the survey by Lang and Xia [START_REF] Lang | Voting in combinatorial domains[END_REF]).

When facing collective decisions with multiple binary issues, the framework of reference is judgment aggregation (see, e.g., List [START_REF] List | The theory of judgment aggregation: an introductory review[END_REF], Lang and Slavkovik [START_REF] Lang | How hard is it to compute majority-preserving judgment aggregation rules[END_REF], and Endriss [START_REF] Endriss | Judgment aggregation[END_REF]). A vast literature explores the computational complexity of this framework [START_REF] Endriss | Complexity of judgment aggregation[END_REF][START_REF] Baumeister | Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules[END_REF][START_REF] De | Complexity results for aggregating judgments using scoring or distance-based procedures[END_REF] and applications range from multiagent argumentation [START_REF] Awad | Judgement aggregation in multi-agent argumentation[END_REF] to the collective annotation of linguistic corpora [START_REF] Qing | Empirical analysis of aggregation methods for collective annotation[END_REF]. However, when considering collective decision-making in practice, the rigidity of representing individual views as complete judgments over issues poses serious obstacles, as becomes evident in the following example inspired by the traveling group problem [START_REF] Klamler | The traveling group problem[END_REF]: Example 1. An automated travel planner is organising a city trip for a group of friends, Ann, Barbara, and Camille, deciding whether to include a visit to a Church, a Museum, and a Park. Ann wants to see all the points of interest, Barbara prefers to have a walk in the Park, and Camille would like to visit a single point of interest but she does not care about which one. A judgment-based automated planner would require agents to specify a full valuation for each of the issues at stake, obtaining the following:

Church Museum Park Ann Barbara × × Camille × ×
The result by majority is a plan to visit both the Museum and the Park. However, Camille voted for the Museum only because asked for a complete judgment, and she was unable to express her truthful goal to "visit a single place, no matter which one" that the result does not satisfy.

The option of allowing individuals to abstain on issues, as proposed by Dietrich and List [START_REF] Dietrich | Judgment aggregation without full rationality[END_REF], and Dokow and Holzman [START_REF] Dokow | Aggregation of binary evaluations with abstentions[END_REF], is easily seen to be insufficient in modelling Camille's preference in Example 1. Moreover, the obvious candidate for aggregating propositional goals, logic-based belief merging [START_REF] Konieczny | Merging information under constraints: A logical framework[END_REF], is quickly ruled out as its rules are not decisive, i.e., they often output a number of equally preferred plans. Building on an original idea of Lang [START_REF] Lang | Logical preference representation and combinatorial vote[END_REF], we use a simple language of propositional goals to model individual preferences, defining and studying several rules to find the most preferred common alternative directly on such input.

A general tension exists in current models of collective decision making in combinatorial domains: on one side is the decisiveness or resoluteness of the rule-i.e., its ability to take a unique decision in most situations-and on the other side are fairness requirements, with respect to issues and individuals. Resoluteness is the primary concern in the development of decision-aid tools such as automated travel planners, or collective product configurators, to avoid returning to the users an excessive number of final options to choose from. Therefore, our purpose is to define rules that are as decisive as possible, whilst keeping high standards of fairness as defined by classical work in social choice and economic theory.

Related work. Judgment aggregation can be seen as goal-based voting in which individuals express single-model propositional goals. This is particularly evident in the binary aggregation model [START_REF] Dokow | Aggregation of binary evaluations[END_REF][START_REF] Grandi | Binary aggregation with integrity constraints[END_REF], and is also true of judgments with abstentions, which correspond to goals specified as partial conjunctions of (possibly negated) variables. Propositional goals have been proposed as compact representations of dichotomous preferences over combinatorial alternatives described by binary variables. Social choice with dichotomous preferences has been widely studied as a possible solution to the computational barriers affecting classical preference aggregation (see, e.g., the recent survey by Elkind et al. [START_REF] Elkind | Structured preferences[END_REF]). However, to the best of our knowledge it has not been applied to combinatorial domains such as those studied in this paper. The vast literature on boolean games [START_REF] Harrenstein | Boolean games[END_REF] studies similar situations in which agents are endowed with propositional goals; yet, our agents do not strategize and they control together the value of the issues at stake. Finally, we acknowledge an attempt at using logic-based belief merging to represent individual goals, using axiomatic properties from belief revision [START_REF] Dastani | Specifying the merging of desires into goals in the context of beliefs[END_REF].

Paper structure. In Section 2 we introduce the framework of goal aggregation, presenting our goal-based voting rules. In Section 3 we list desirable properties for such rules, and prove a characterisation result. In Section 4 we analyse the computational complexity of determining the winner of goal-based voting, and in Section 5 we conclude.

Goal-Based Voting

We begin with basic definitions and we introduce voting rules for goal-based collective decisions in multi-issue domains.

Basic Definitions

Let N = {1, . . . , n} be a set of agents deciding over a set I = {1, . . . , m} of binary issues or propositions. Agent i has individual goal γ i , expressed as a consistent propositional formula over variables in I (using standard connectives ∧, ∨, → and ¬). For instance, in Example 1 Camille's individual goal is γ 3 = (1 ∧ ¬2 ∧ ¬3) ∨ (¬1 ∧ 2 ∧ ¬3) ∨ (¬1 ∧ ¬2 ∧ 3), since she wants to visit a single place.

An interpretation is a function v : I → {0, 1} associating a binary value to each propositional variable. We often visualise v as the vector (v(1), . . . , v(m)). The set Mod(ϕ) = {v | v |= ϕ} consists of all the models of formula ϕ. A goal is exponentially more succint than the set of its models. In voting terminology, interpretations correspond to alternatives, and models of γ i are the alternatives supported by agent i. We assume that issues in I are independent, i.e., all interpretations over I are feasible alternatives. We indicate by m i (j) = (m1 ij , m 0 ij ) the number of 1/0 choices of agent i for issue j in the different models of her goal γ i , where m x ij = |{v ∈ Mod(γ i ) | v(j) = x}| for x ∈ {0, 1}. For example, if Mod(γ 1 ) = {(100), (010), (001)} for issue j = 3 we have m 1 (3) = (m 1 13 , m 0 13 ) = (1, 2). A goal-profile Γ = (γ 1 , . . . , γ n ) collects the goals of all agents in N and a goal-based voting rule is a function taking a goal-profile and returning a set of interpretations as the collective outcome. Formally, it is a collection of functions F : (L I ) n → P({0, 1} m ) \ ∅ defined over any n and m whose input are n formulas submitted by the agents, and whose output is a set of models over the m issues in I.

If a rule always outputs a singleton we call it resolute, and irresolute otherwise. We let

F (Γ) j = (F (Γ) 0 j , F (Γ) 1 j ), where F (Γ) x j = |{v ∈ F (Γ) | v j = x}| for x ∈ {0, 1}, indicate the amount of 0/1 choices in the outcome of F for j. We write F (Γ) j = x in case F (Γ) 1-x j = 0 for x ∈ {0, 1}.

Conjunction and Approval Rules

We begin by introducing the following baseline rule:

Conj v (Γ) = Mod(γ 1 ∧ • • • ∧ γ n ) if non-empty {v} for v ∈ {0, 1} m otherwise
The conjunction rule is an irresolute rule that outputs those alternatives on which all agents agree, and a default otherwise. While such consensual alternatives are clearly an optimal choice, they rarely exist-the purpose of voting being to find compromises among conflicting individual goals.

To avoid default options, we introduce the following rule:

Approval (Γ) = arg max v∈Mod( i∈N γi) |{i ∈ N | v ∈ Mod(γ i )}|.
This rule expresses simple approval voting [START_REF] Brams | Approval voting[END_REF][START_REF] Laslier | Handbook on Approval Voting[END_REF]. It is also studied by Lang [START_REF] Lang | Logical preference representation and combinatorial vote[END_REF] as the plurality rule, and in belief merging as an instance of ∆ ,d µ -rules by Konieczny and Perez [START_REF] Konieczny | Merging information under constraints: A logical framework[END_REF]. Despite its intuitive appeal, approval-based voting is not adapted to combinatorial domains in which a large number of alternatives might be approved by a few agents only.

Issue-Wise Voting

We first introduce a large class of goal-based rules inspired by the well-known quota rules from judgment aggregation [START_REF] Dietrich | Judgment aggregation by quota rules: Majority voting generalized[END_REF]. Let µ ϕ : Mod(ϕ) → R be a function associating to each model v of ϕ some weight µ ϕ (v), giving (possibly) different weights to distinct models of the same formula. Let threshold rules be defined as follows:

TrSh µ (Γ) j = 1 iff i∈N (w i • v∈Mod(γi) v(j) • µ γi (v)) ≥ q j
such that 1 ≤ q j ≤ n for all j ∈ I is the quota of issue j, where for each v ∈ Mod(γ i ) we have µ γi (v) = 0 and w i ∈ [0, 1] is the individual weight of agent i. To ease notation we omit the vector q = (q 1 , . . . , q m ) from TrSh µ , specifying the particular choice of thresholds for the issues. Intuitively, threshold rules set a quota to be passed for each issue to be accepted, with the additional flexibility of weights for agents and for models of the individual goals.

From here, we can provide a first adaptation of the classical issue-wise majority voting for goalbased settings. Inspired by equal and even cumulative voting [START_REF] Campbell | The origin and growth of cumulative voting for directors[END_REF] we call EQuota rules those TrSh µ procedures having

µ γi (v) = Γ 1 Γ 2 Γ 3
Mod(γ A second (irresolute) version of majority voting simply compares for each issue the number of acceptances with the number of rejections, weighting each goal model as EQuota:

TrueMaj (Γ) = Π j∈I M (Γ) j
where for each j ∈ I:

M (Γ) j = {x} if i∈N m x ij |Mod(γi)| > i∈N m 1-x ij |Mod(γi)| {0, 1} otherwise
Intuitively, TrueMaj computes a weighted count of the 1s and the 0s in all models of the individual goals, discounted by the number of models of the formula sent by the agent. In case of ties on an issue, the rule outputs all interpretations with either 0 or 1 for that issue. We define a third version of the majority rule as 2sMaj(Γ) = Maj (Maj (γ 1 ), . . . , Maj (γ n )), where Maj is the classical issue-by-issue strict majority rule, that accepts an issue if and only if a strict majority of the models of γ i does. This procedure belongs to a wider class of rules that can be obtained by applying a first rule on each individual goal, and a second, possibly different, rule on the results obtained in the first step.

We now prove that the three proposed versions of goal-based majority do not always return the same result. Proposition 1. There exists goal-profiles on which the outcomes of EMaj , TrueMaj and 2sMaj differ.

Proof sketch. In Table 1 we provide a profile for each pair of rules on which their results differ. Consider Γ 1 and EMaj . For agents 1 and 2, the weight of the single model satisfying their goal is 1, while for the third agent is

1 |Mod(γ3)| = 1
3 . If we focus on the first issue,

m 1 11 |Mod(γ1)| + m 1 21 |Mod(γ2)| + m 1 31 |Mod(γ3)| = 1 + 2 3 < 2, hence EMaj (Γ 1 ) 1 = 0. Take TrueMaj instead. Since i∈N m 1 i1 |Mod(γi)| = 1 + 2 3 > 1 + 1 3 = i∈N m 0 i1 |Mod(γi)| we get TrueMaj (Γ 1 ) 1 = 1.
The calculations for the other cases can be obtained straightforwardly.

Axiomatic Analysis

In this section we conduct an axiomatic analysis of the proposed rules and we provide a characterisation of TrueMaj .

Axiom Definitions

A first straightforward generalisation of an axiom from the literature on Social Choice Theory is the following: Definition 1. A rule F is anonymous (A) if for any profile Γ and permutation σ : N → N , we have that F (γ 1 , . . . , γ n ) = F (γ σ(1) , . . . , γ σ(n) ).

Observe that all the presented rules are anonymous, except for threshold rules with varying weights for the agents.

Define ϕ[j → k] for j, k ∈ I as the replacement of each occurrence of j by k in ϕ. The next axiom ensures that issues are treated equally:

Definition 2. A rule F is neutral (N) if for all Γ and σ : I → I, we have F (γ σ 1 , . . . , γ σ n ) = {(v(σ(1)), . . . , v(σ(m))) | v ∈ F (Γ)} where γ σ i = γ i [1 → σ(1), . . . , m → σ(m)].
TrSh µ and EQuota rules are not neutral when the quotas for two issues differ. Neither is Conj v , by permuting issues in a profile of inconsistent goals resulting in a profile of inconsistent goals, so that the same default v is chosen. Approval is neutral, since the values for the issues are permuted in the models of the agents' goals. Both TrueMaj and 2sMaj have the same quota for all issues, and hence they are neutral.

We then move to a controversial yet well-known axiom in the literature, used in both characterisation and impossibility results [START_REF] List | The theory of judgment aggregation: an introductory review[END_REF][START_REF] Brandt | Handbook of Computational Social Choice[END_REF].

First, let

D m = {(a, b) | a, b ∈ N and a + b ≤ 2 m } and C = {{0}, {1}, {0, 1}}
. Independence is formally defined as: Definition 3. A rule F is independent (I) if there are functions f : D n m → C for j ∈ I such that for all profiles Γ we have F (Γ) = Π j∈I f (m 1 (j), . . . , m n (j)).

Albeit being often identified as one of the main sources of impossibilities in aggregation theory [START_REF] List | The theory of judgment aggregation: an introductory review[END_REF], we believe that independent (i.e., issue-wise) rules are crucial in solving the tension between fairness and resoluteness in goal-based voting. From the definitions we easily see that TrSh µ , EQuota and TrueMaj are independent, while Conj v and Approval are not since they consider the profile globally.

The next axiom holds whenever the unanimous choice of the agents for an issue is respected in the outcome: Definition 4. A rule F is unanimous (U) if for all profiles Γ and for all j ∈ I, if m x ij = 0 for all i ∈ N then F (Γ) j = 1 -x for x ∈ {0, 1}.

While if all agents accept or reject an issue the output of TrueMaj and 2sMaj will agree with the profile, interestingly TrSh µ and EQuota rules do not satisfy it (by setting a high enough quota) as well as Conj v (for a profile where goals are inconsistent and thus the default is chosen).

We say that profiles Γ and Γ are comparable if and only if for all i ∈ N we have that |Mod(γ i )| = |Mod(γ i )|. Then, a rule is positively responsive if adding (deleting) support for issue j when the result for j is equally irresolute or favouring acceptance (rejection), results in an outcome stricly favouring acceptance (rejection) for j. Definition 5. A rule F satisfies positive responsiveness (PR) if for all comparable profiles Γ = (γ 1 , . . . , γ i , . . . , γ n ) and Γ = (γ 1 , . . . , γ i , . . . , γ n ), for all j ∈ I and i

∈ N , if m x ij ≥ m x ij for x ∈ {0, 1}, then F (Γ) 1-x j ≥ F (Γ) x j implies F (Γ ) 1-x j > F (Γ ) x j .
Observe that all our presented versions of majority are positively responsive, since they have a threshold of acceptance.

We conclude by presenting two important fairness axioms. The first aims at formalising the "one man, one vote" principle, and ensures that a rule is giving equal weight to the models of each individual goal for all the agents. It is satisfied by all EQuota rules as well as by TrueMaj : The second axiom instead focuses on possible biases towards acceptance or rejection of the issues.

Definition 7. A rule is dual (D) if for all profiles Γ, F (γ 1 , . . . , γ n ) = {(1 -v(1), . . . , 1 -v(m)) | v ∈ F (Γ)} where γ = γ[¬1 → 1, . . . , ¬m → m].
A similar requirement is called neutrality by May [START_REF] May | A set of independent necessary and sufficient conditions for simple majority decision[END_REF], while in binary aggregation this is known as domain-neutrality [START_REF] Grandi | Binary aggregation with integrity constraints[END_REF].

Characterising Goal-Based Majority Rules

A seminal result in characterising aggregation rules is May's Theorem [START_REF] May | A set of independent necessary and sufficient conditions for simple majority decision[END_REF], where an axiomatisation of the majority rule in the context of voting over two alternatives is provided. A natural question to ask after defining three versions of the majority rule is therefore whether one can be axiomatised, building on May's results. We answer this question in the positive: Theorem 1. A rule F satisfies (E), (I), (N), (A), (PR), (U) and (D) if and only if it is TrueMaj .

Proof. Right-to-left follows from discussion in Section 3.1. For left-to-right, consider a rule F . Let Γ be an arbitrary profile over n voters and m issues. By (E), we can construct a profile Γ for m issues and n agents, where n is as in Definition 6, in which each agent submits a single-model goal and such that v ∈ F (Γ) if and only if v ∈ F (Γ ). We therefore consider the restriction of F on profiles over n agents and m issues where agents submit single-model goals. We denote G such a set of profiles (hence, in particular, Γ ∈ G ). We now show that F (Γ ) = TrueMaj (Γ ).

By (I), there are functions f 1 , . . . , f m such that

F (Γ ) = f 1 (m 1 (1), . . . , m n (1)) × • • • × f m (m 1 (m), . . . , m n (m)).
Observe that since Γ ∈ G , we have m i (j) ∈ {(0, 1), (1, 0)} for all i ∈ N and j ∈ I. Hence, we can equivalently see each f on profiles in G as a function from {0, 1} n to C. By (N) and (I) we get that f 1 = • • • = f m , i.e., the same function applies to all issues, let us denote it with f . By (A), any permutation of agents in Γ gives the same result F (Γ ). Hence, combining (A) with (I) and (N), we have that only the number of ones (and zeroes) and not their position is necessary to determine the outcome of f . Hence, we can write it as f : {0, . . . , n} → C.

Consider now a profile Γ + ∈ G such that for all i ∈ N we have m 0 ij = 0. By (U) we know that F (Γ) 0 j = 0, i.e., v(j) = 1 for all v ∈ F (Γ), and consequently that f (n) = {1}. Analogously we obtain that f (0) = {0}.

Let now s be a sequence of G -profiles Γ -= Γ 0 , Γ 1 , . . . , Γ n = Γ + where exactly one agent i at a step k changes her goal γ i such that

m 1 ij = 0 in Γ k and m 1 ij = 1 in Γ k+1
. By (I) and the definition of cartesian product, for any Γ and j, F (Γ) j is either equal to (a, 0), (b, b) or (0, c) for a, b, c ∈ N.

By (PR), the outcome of the Γ k profiles in s can only switch from (a, 0) to (b, b) or (0, c), and from (b, b) to (0, c). In particular, this means that there is some number q such that f (0) = {0}, . . . , f (q -1) = {0}, f (q) = {0, 1} or f (q) = {1}, and f (q + 1) = {1}, . . . , f (n) = {1}.

We now show that for n even, q = n 2 and f (q) = {0, 1}, while for n odd we have q = n+1 2 and f (q) = {1}. For n even, consider profile Γ where exactly half of the agents accept j. If F (Γ ) j = (0, a) or (c, 0), by (D) we would need to reverse the outcome in F (Γ ) j . However, the decision in both profiles is determined by f ( n 2 ), which is therefore equal to {0, 1}. For n odd, suppose that q < n+1 2 and consider a profile Γ where there are exactly q agents accepting j. By (PR) we have F (Γ) j = (0, c). Consider now profile Γ: we have |{i | m i (j) = (0, 1)

for γ i ∈ Γ}| = |{i | m i (j) = (1, 0) for γ i ∈ Γ}| = q < n+1 2 . Hence, |{i | m i (j) = (0, 1) for γ i ∈ Γ}| ≥ n+1 2
> q. Hence, F (Γ) j = (0, c), contradicting (D). Suppose q > n+1 2 and consider a profile Γ where n+1 2 ≤ |{i | m i (j) = (0, 1) for γ i ∈ Γ}| < q. Then, F (Γ) j = (a, 0) and F (Γ) j = (a, 0), again contradicting (D).

To sum up, F is defined as the cartesian product of binary decisions taken by the same function f : {0, . . . , n} → C. on each issue, with f (k) = {0, 1} for n even and k

= n 2 , f (k) = {0} for i∈N m x ij > i∈N m 1-x ij for x ∈ {0, 1}
, corresponding to the definition of TrueMaj . Since Γ is an arbitrary goal profile, and TrueMaj satisfies (E), we obtained the desired equivalence.

While both EMaj and 2sMaj are based on similar intuitions as TrueMaj , EMaj has a bias towards the rejection of the issues, while 2sMaj does not satisfy the equality axiom. TrueMaj however remains the only irresolute rule of the three, once more showing the tension between fairness criteria and the decisiveness of a goal-based voting rule.

We conclude with a seemingly negative result. A rule is Hence, the three majority rules do not guarantee that the collective choice will satisfy the goal of at least one agent. However, by considering aggregation as compromising between agents, it becomes less important for a rule to be grounded.

grounded if v ∈ F (Γ) implies v ∈ Mod(γ 1 ∨ • • • ∨ γ n ).

Computational Complexity

In this section we study the computational complexity of determining the result of goal-based voting, showing that propositional goals entail a significant increase from standard voting, in some cases from P to Probabilistic Polynomial time.

Winner Determination

We present two definitions for the winner determination problem, for resolute and irresolute rules, in line with the literature on judgment aggregation [START_REF] Endriss | Complexity of judgment aggregation[END_REF][START_REF] Baumeister | Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules[END_REF][START_REF] De | Complexity results for aggregating judgments using scoring or distance-based procedures[END_REF].

Note that we provide the existential version of the winner determination problem -a universal definition is also possible [START_REF] Lang | How hard is it to compute majority-preserving judgment aggregation rules[END_REF]. We start with resolute rules: WINDET(F ) Input: profile Γ, issue j Question: Is it the case that F (Γ) j = 1?

The outcome for F (Γ) can then be computed by repeatedly answering the question in WINDET over all issues j ∈ I. Next, we introduce the problem for irresolute rules.

WINDET (F )

Input: profile Γ, set S ⊆ I, partial model ρ : S → {0, 1} Question: Is there a v ∈ F (Γ) with v(j) = ρ(j) for j ∈ S?

By answering to the question in WINDET starting from a set S with one issue and filling it with all the issues in I, and checking possible values for the partial function ρ we can construct a complete model in the outcome of F (Γ).

Question: Is it the case that |Mod(ϕ ∧ p)| > |Mod(ϕ ∧ ¬p)|?

We first show that MAJ-SAT-p is PP-complete by reducing from the PP-complete MAJ-SAT, the problem of deciding whether a formula ϕ has more models than its negation. Lemma 2. MAJ-SAT-p is PP-complete.

Proof. We start by showing membership in PP. Consider the non-deterministic Turing machine that guesses a model v for ϕ. Then, if v |= ϕ the machine accepts with probability 1 2 . If v |= ϕ ∧ p the machine accepts with probability 1 and if v |= ϕ ∧ ¬p the machine accepts with probability 0.

For completeness, we reduce from MAJ-SAT. Consider the formula ϕ as our instance of MAJ-SAT, and now let ψ = (ϕ∧p)∨(¬ϕ∧¬p) for p a fresh variable. We can now observe that ϕ has more models than ¬ϕ if and only if ψ ∧ p has more models than ψ ∧ ¬p, concluding the reduction.

The next theorem gives a lower bound to computing the outcome of the majority rules. Note that for TrueMaj we study a (strict) resolute version TrueMaj r . Theorem 5. WINDET(2sMaj ), WINDET(EMaj ) and WINDET(TrueMaj r ) are PP-hard.

Proof. The proof is analogous for the three rules, so we only prove it for 2sMaj . We reduce from MAJ-SAT-p. Consider the formula ϕ and the variable p of ϕ as our instance of MAJ-SAT-p. Consider now a profile Γ for a single agent such that γ 1 = ϕ. Since we are dealing with resolute rules, we simply have to fix an issue and ask whether the goal-based voting rule will accept or reject the issue. Given that there is a single agent 1, we have that 2sMaj (Γ) p = 1 if and only if the set of models of γ 1 accepts p more often than reject it. Therefore, ϕ ∧ p has more models than ϕ ∧ ¬p if and only if 2sMaj (Γ) p = 1, completing the reduction.

While PP is the hardest class studied in this paper, the axiomatic analysis of Section 3 as well as their intuitive definitions make us champion our majority-based rules, and TrueMaj in particular. We argue that the class PP is pervasive in propositional goal-based reasoning, calling for the development of good algorithms for problems in this class.

Conclusions and future work

Starting from the observation that classical judgment aggregation falls short in many examples of collective decision-making in multi-issue domains, such as creating a shared travel plan or collective product configuration, we introduced new rules to aggregate a set of propositional goals into a collectively satisfying alternative. In a quest for resolute rules, we introduced three adaptations of the classical majority rule, as well as other goal-based voting rules, providing an axiomatic characterisation in line with the literature on Social Choice Theory for one of them (TrueMaj ). We concluded by investigating the computational complexity of determining the outcome of our rules, showing that the use of propositional goals entails harder complexity classes.

Our results open several paths for future research, most notably in studying restrictions on the language of goals that might determine islands of tractability for the winner determination problem, or develop tractable approximations for their computation. Moreover, the quest for more resolute and decisive rules may suggest novel voting procedures in related areas such as non-binary combinatorial domains and more expressive compact languages for preference representation. Finally, we focused on the basic case of no integrity constraints, but it would be interesting to study classes of constraints for which our rules always return consistent results.

Definition 6 .

 6 A rule F is egalitarian (E) if for all Γ, on the profile Γ with |N | = |N | • lcm(|Mod(γ 1 )|, . . . , |Mod(γ n )|), and for all i ∈ N and v ∈ Mod(γ i ) there are |N | |N |•|Mod(γi)| agents in Γ having goal γ with Mod(γ) = {v}, it holds that F (Γ) = F (Γ ).

Proposition 2 .

 2 EQuota, TrueMaj and 2sMaj are not grounded. Proof. Consider profile Γ for 3 agents and 3 issues where Mod(γ 1 ) = {(111)}, Mod(γ 2 ) = {(010)} and Mod(γ 3 ) = {(001)}. Both EQuota (with uniform quota 2), TrueMaj and 2sMaj return (011), contradicting groundedness.

Table 1 :

 1 Three goal-profiles on which majority-based rules differ.

	1 ) (111) (111) (000)
			(111) (111)
	Mod(γ 2 ) (001) (011) (110)
			(000) (011)
		(100) (111) (111)
	Mod(γ 3 ) (010) (011) (110)
		(101) (000) (011)
	EMaj	(001)	-	(010)
	TrueMaj (101) (111)	-
	2sMaj	-	(011) (111)

|Mod(γi)| and w i = 1 for all v ∈ Mod(γ i ) and for all i ∈ N . Thus, the equal and even majority rule EMaj is the EQuota rule having q j = n

for all j ∈ I.

Acknowledgments

We are grateful to the AAMAS and IJCAI reviewers, as well as to Jérôme Lang and Ronald de Haan for their helpful comments. This work was partially supported by the project "Social Choice on Networks" of Labex CIMI ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02.

Conjunction and Approval Rules

Our first complexity result provides a lower bound for the family of conjunction rules Conj v (Γ). Proof. We reduce from SAT. Let ϕ [p 1 , . . . , p k ] be the formula over k variables whose satisfiability we want to check. Construct an instance of WINDET(Conj v ) as follows. Let I = {p 1 , . . . , p k } ∪ {q}. Consider a profile Γ = (γ 1 ) for a single agent 1, such that γ 1 = q ⊕ ϕ , for ⊕ the exclusive or. This formula is true if and only if either q is true or ϕ is true, so that the default model v is not needed. If we set S = {q} and ρ(q) = 0, we get that ϕ is satisfiable if and only if for this instance of WINDET (Conj v ) the answer is yes.

Membership in NP is still open. The intuitive algorithm that guesses a model v, then checks whether

¬j (i.e., the formula expressing ρ), excludes the case in which the conjunction of the goals is satisfiable, but v is not a model.

The Approval rule is significantly harder. We first need some definitions. Let Θ p 2 = P NP[log] be the class of decision problems solvable in polynomial time by a Turing machine that can make O(log n) queries to an NP oracle, for n the size of the input. Consider the following Θ p 2 -complete problem [START_REF] Chen | The complexity of selecting maximal solutions[END_REF]: MAX-MODEL Input: satisfiable propositional formula ϕ, variable p of ϕ Question: Is there a model v ∈ Mod(ϕ) that sets a maximal number of variables of ϕ to true and such that v(p) = 1?

We are now ready to prove the following:

Proof. Membership in Θ p 2 can be obtained from Proposition 4 by Lang [START_REF] Lang | Logical preference representation and combinatorial vote[END_REF], using the following formula in the definition of the ELECT-SAT problem:

For completeness, we give a reduction from MAX-MODEL. Consider an instance of MAX-MODEL where ϕ[p 1 , . . . , p m ] is a satisfiable formula and p i for i ∈ {1, . . . , m} is one of its variables. Construct now an instance of WIN-DET (Approval ) in the following way. Let Γ = (γ 1 , . . . , γ m+1 , γ m+2 , . . . , γ 2m+1 ) be a profile such that

We have that Approval (Γ) ⊆ Mod(ϕ), since a strict majority of m+1 2m+1 agents already supports all the models of ϕ. Moreover, note that in this instance of Approval precisely the models maximising the number of variables set to true in ϕ win. In fact, consider a model v ∈ Mod(ϕ): as explained, v gets the support of all the first m + 1 agents whose goal is ϕ, and then for all the agents in {m + 2, . . . , 2m + 1} it gets the support of those agents whose goal-variable is true in v. Specifically, the support of v is (m + 1)

Hence, only those v ∈ Mod(ϕ) with a maximal number of 1s are in the outcome of Approval (Γ). It now suffices to set S = {p i } for p i the propositional variable in the instance of MAX-MODEL and ρ(p i ) = 1. Therefore, a formula ϕ has a model with a maximal number of variables set to true where p i is true if and only if WINDET (Approval ) returns yes on the constructed input.

Threshold Rule

We study the complexity of finding the outcome of TrSh µ rules for the special case where each model, as well as each agent, has the same weight of 1. We start by studying the following auxiliary problem.

k-MODELSUM

Input: propositional formulas ψ 1 , . . . , ψ , number k ∈ N Question: Is it the case that 1≤i≤ |Mod(ψ i )| > k?

We now find the complexity for k-MODELSUM.

Proof. To show membership in NP guess k 1 , . . . , k numbers with k i ≤ k + 1 for all 1 ≤ i ≤ , and guess X 1 , . . . , X sets, where X i ⊆ 2 |Var | for 1 ≤ i ≤ and Var is the set of variables of ψ 1 , . . . , ψ . The size of each X i for 1 ≤ i ≤ is bounded by k + 1, and each X i corresponds to a set of models. It is then easy to check that k

For completeness, we reduce from SAT. Let ϕ be the formula whose satisfiability we want to check. Construct now an instance of k-MODELSUM where ψ 1 = ϕ and k = 1. Formula ϕ is satisfiable if and only if it has at least one model, and SAT can be reduced to k-MODELSUM.

Now we can assess the complexity of the rule TrSh

Proof. For membership in NP consider a profile Γ = (γ 1 , . . . , γ n ) and an issue j. Guess k 1 , . . . , k n numbers with k i ≤ k + 1 for 1 ≤ i ≤ n, and guess X 1 , . . . , X n sets of models where X i ⊆ 2 m and for each v ∈ X i we have v(j) = 1 for i ∈ N . It is then easy to check whether k 1 + • • • + k n > q j , that for all i ∈ N we have |X i | = k i and for all v i ∈ X i we have v i ∈ Mod(γ i ).

For completeness, we reduce from k-MODELSUM. Let ψ 1 , . . . , ψ and k ∈ N be an instance of this problem. Construct now an instance of WINDET(TrSh µ ) such that Γ = (γ 1 , . . . , γ ) where for all i ∈ N we have γ i = ψ i ⊕ ¬p for p a fresh variable and ⊕ the exclusive or. This is done since the formulas of the k-MODELSUM might be inconsistent, while individual goals are always consistent. Now, we choose j = p and we set q j = k. In this way, every model v such that v(p) = 1 is a model of ψ i for all i ∈ N , and we can thus count if there are at least k models of each ψ i , which give TrSh µ (Γ) p = 1.

While it would be easy to adapt this proof to deal with different values for the individual weights w i (to be multiplied with the k i 's), for model weights as the ones in EQuota rules it would be necessary to compute the number of models of each goal, thus making it a more difficult problem.

Majority Rules

We now study the complexity of majority rules. We introduce the complexity class PP, for Probabilistic Polynomial Time, a class of problems that has rarely been encountered in the literature on computational social choice, and we show that the three versions of the majority rule are PP-hard.

Membership is an open problem for future work.

Let PP be the class of decision problems solvable by a non-deterministic Turing machine that accepts in strictly more than half of all non-deterministic choices if and only if the answer to the problem is yes [START_REF] Papadimitriou | Computational Complexity[END_REF]. Consider the following problem: MAJ-SAT-p Input: propositional formula ϕ, variable p of ϕ


Michael Hemmer

Cédric Google

Portaneri

Alpha Hulls

Accurate and valid 3D digital representations are required for digital twins of production facilities and robotic applications. In this project we consider settings where the input 3D geometry is limited to boundary representations in the form of triangle soups, defect-laden and with overly high resolution. We address the problem of converting such defect-laden inputs into valid solid representations with just-enough details for enabling efficient processing.

Defects. The input 3D geometry that needs to be processed is often overly detailed yet imprecise and invalid. More specifically, the input triangle soups are either automatically generated from CAD models or reconstructed from laser scanned point sets. Most of these models fall short on providing a consistent (valid) boundary representation of the physical real world objects they are supposed to model. Beyond outliers, such as missing or ill-placed triangles, the most common defects are open boundary edges of triangular patches that do not match their corresponding counterparts, which results in gaps, islands or self intersections.

While this can be tolerated to some extent for collision detection in which the geometric primitives are anyway organized in an acceleration data structure such as a bounding volume hierarchy, grid or octree, it is very inconvenient to have an inconsistent boundary representation. For instance, the notion of exterior and interior of an object are inherently ill-defined and tasks such as "remove inner geometry", "provide a conservative simplification", "compute thickness" or "swept volume computations" are either a gamble and/or are significantly slowed down.

Aiming for an industrial product at Google scale it is extremely important to stress the fundamental role that the geometry processing will play for our project/Ballet. Considering that the problem definition of one cell from the recent pilot had around 45k geometric objects it is clear that even a seemingly low failure rate of just 0.01% would impact the scalability of the product. Therefore, in order to achieve robustness, the geometric processing package has been refactored to follow the Exact Geometric Computing Paradigm in order to eliminate additional uncertainty that would be introduced by solely implemented algorithms using error prone floating point arithmetic.

Requirements. We have identified two crucial geometric processing tasks for our project. Since the meshes that are given to us are not precise and topological inconsistent, we need an operator that converts those into valid solids, that is, each solid object must be represented by a closed triangular mesh that is free of self intersections (and therefore orientable). Such valid 3D models offers a well-defined notion of inside and outside and allows further processing. In addition, the resulting mesh must strictly contain the input (i.e., be conservative) so that we can guarantee that we are not violating any constraints (such as safety margins). In addition, we must remain tight to the input, that is, we should not add extra material everywhere, as this would make the robot motion planning problem harder and in the worst case even infeasible.

In short, we require a tight solid outer approximation of the input. We define next these three notions.

• Tight. By tight we express that we can not afford to achieve this by, e.g., simply providing a uniform offset surface of some large epsilon as this would make the underlying robot motion planning problem much harder. Inflating objects would shrink the free configuration space and in extreme cases render the motion planning problem infeasible. • Solid. In the literature a solid is commonly referred to as a shape that could also exist in the physical real world. Specifically, it must be bounded by a closed surface, have no low dimensional features and provide a well-defined notion of interior and exterior. Thus, a valid boundary representation (usually a surface mesh) conforming to such a solid definition is a closed 2-manifold that is free of self intersections.

• Outer Approximation. Outer approximation (also commonly referred to as conservative approximation) implies that the resulting solid object must strictly contain the original input triangle soup. Such a conservative approach ensures that the robots never collides the physical objects in order to obey all safety requirements.

Related Work

The quest for conservative approximations has generated a series of contributions [START_REF] Kalvin | Superfaces: Polygonal mesh simplification with bounded error[END_REF][START_REF] Cohen | Simplification envelopes[END_REF][START_REF] Guéziec | Surface simplification inside a tolerance volume[END_REF][START_REF] Ciampalini | Multiresolution decimation based on global error[END_REF][START_REF] Zelinka | Permission grids: Practical, error-bounded simplification[END_REF][START_REF] Cohen | Successive mappings: An approach to polygonal mesh simplification with guaranteed error bounds[END_REF][START_REF] Botsch | GPU-based tolerance volumes for mesh processing[END_REF][START_REF] Borouchaki | Simplification of surface mesh using hausdorff envelope[END_REF][START_REF] Mandad | Isotopic Approximation within a Tolerance Volume[END_REF], and converting a triangle soup from the wild into a valid solid approximation even without further guarantees is still an active area of research [START_REF] Hu | Tetrahedral meshing in the wild[END_REF]. The approach entitled "Tetrahedral Meshing in the Wild" compares with three algorithms currently available in the CGAL library [START_REF]CGAL User and Reference Manual[END_REF]. However, and while the results are indeed impressive from the robustness point of view this approach has one fundamental flaw. It uses winding numbers to eventually define which cells of the 3-dimensional triangulation are considered inside and outside. The notion of winding number utilized in this approach is inherently a heuristic, which is not appropriate for our context as there is no guarantee that the result contains the input.

Alpha Hull

The term alpha hull has first been introduced by Herbert Edelsbrunner. The alpha hull as defined in the PhD manuscript of Herbert Edelsbrunner is the complement of the union of all open balls of radius alpha that do not contain a point of the input. The alpha shape is considered as the linearization of this shape. The term is still used in the context of generalizations of the alpha shape, that is, for weighted input points to for instance approximate the shape of molecules.

The alpha hull has certainly been studied before as a mathematical object. This is not a surprise as it is a rather straightforward generalization of the convex hull. The convex hull, in short, is the closure of the union of all segments defined by all possible pairs of points from the input, where closure means that one repeats this process until the set does not change anymore. E.g. for an input in 3D, one may need up to three rounds. The alpha hull is a generalization of the convex hull in the sense that it is defined as the union of all convex hulls of the input within balls of radius alpha.

Definition. For an input set S, the alpha hull with scalar parameter alpha, in short AH(S,alpha), is defined as the infinite union of all convex hulls of the input within a ball of radius alpha

AlphaHull(S, α) = ∀ x∈R 3 (CH(Ball(x, α) ∩ S))

Remarks

• The definition is not constructive as there are as many balls as there are points in R3.

• The alpha hull is not defined as a closure.

• The alpha Hull is not a simplicial complex, i.e. not composed solely of points, line segments and triangles.

• A major flaw of alpha hulls which makes them rather inconvenient to handle is that they induce concave surface patches in concave parts of the input object. That is, even though the input is a set of triangles, the operator leaves the realm of surfaces that can be again represented by triangular meshes (aka simplicial complexes).

• The Alpha Hull is not idempotent as in general, the alpha hull of an input alpha hull and the input alpha hull are not the same. Specifically, the closure of the alpha hull operator results in a set of convex hulls.

Alpha hull vs alpha shape. The notion of Alpha Hull should not be confused with the one of the Alpha Shape, which is only defined for a point set P . The Alpha Shape is conveniently defined on top of the Delaunay Triangulation of P , as the set triangles of the Delaunay Triangulation whose vertices can be touched by a ball of radius alpha while not actually containing any of the points in P , including the three points of the triangle which must lie on the boundary of the ball. While not going into details this can lead to configurations where, for a point set P, a triangle that fits into a ball with radius alpha (and therefore is part of the Alpha Hull) is not part of the Alpha Shape. We are not aware of a generalization of alpha shapes to inputs other than points as its definition is based on Delaunay Triangulation, which is defined for point sets only.

Implementation

We implemented the approximate alpha hull algorithm using the CGAL library and exact arithmetic.

Our algorithm takes a input a surface triangle mesh and a user-defined scalar alpha value. There is no prerequisite on the input connectivity so that it can take an arbitrary triangle soup, with self-intersections. It generates as output either a watertight surface triangle mesh whose interior volume strictly encloses the input triangle soup, or a message stating that the input is not alpha valid, in the sense that it contains holes larger than alpha.

Algorithm. The algorithm starts by inserting all input vertices into a 3D Delaunay triangulation. It then performs an initial point sampling through recursive longest edge bisection applied to the facets of the input triangle soup, for which the smallest enclosing sphere radius is larger than alpha/2, and as long as the facet is not already represented in the Delaunay triangulation. All those new sample points are added to the Delaunay triangulation. In the Delaunay triangulation from the CGAL library, all triangle facets are adjacent to two tetrahedron cells. Each facet of the boundary of the Delaunay triangulation, which coincides with one facet of the convex hull of the triangulation vertices, is adjacent to one so-called infinite tetrahedron cell, an abstract cell connected to a so-called infinite vertex to ensure the aforementioned double facet adjacency. The algorithm then proceeds to flood fill, which consists of a BFS traversal of the cells of the Delaunay triangulation. Initially, all cells are tagged as inside except the infinite cells that are tagged outside. Flood filling consists of traversing the cells via the adjacency graph between cells, starting from the infinite ones tagged as outside, and tagging the traversed cells as outside whenever possible. Given a cell and its neighbor cell, we can visit its neighbor if the facet between them is not part of the input and if its smallest enclosing sphere is larger than alpha. Once the neighbor cell is visited, we tag it as outside and resume traversal only when the neighbor cell does not intersect the input triangle soup in a non-conforming way. If it does, we insert a sample point into the Delaunay triangulation at the intersection between this neighbor cell and the input to trigger a cell removal through Delaunay insertion. We resume the flood fill considering the newly created cells.

In order to know whether a Delaunay facet is part of the input triangle soup, or to know whether the neighbor cell is intersecting the input in a non conforming way, we devised a specific data structure that represents the input. For each set of coplanar faces of the input, we construct a constrained 2D Delaunay triangulation in 3D where each vertex is mapped to the 3D Delaunay triangulation. Because the two types of Delaunay triangulation have most of the time the same connectivity locally, we can efficiently check whether a 3D facet exists or whether a 3D cell is conforming in this space of 2D triangulations.

Figure 3: Dealing with non conforming cases. Left: given some constrained edges (blue), a Delaunay triangulation is non-conforming when its edge (green) does not cover all the constraints. Right: case where the volume of the input geometry in the middle is so thin that it is not represented in the Delaunay triangulation. In this case the flood fill tags both adjacent cells of those non represented facets as exterior.

Output. The output is a surface mesh that represents the outer boundary of the hull. It has the same properties as the hull itself as it contains the input and is bounding a volume. It is tight in convex areas and has spurious volume elements in concave areas. The Hausdorff distance from the output mesh to the input is at most equal to the alpha value. The output is combinatorially manifold as it is extracted from the Delaunay triangulation, but it can contain non-manifold edges, always adjacent to an even number of face. The output mesh geometry is represented via exact numbers in order to ensure all above properties. In theory, converting such numbers to double precision numbers might yield self-intersections and a volume not containing the input anymore.

Figure 1 :

 1 Figure 1: Geometry sanitizer. Left: defact-laden bunny. Right: output alpha hull.

Figure 2 :

 2 Figure 2: Flood fill algorithm. from left to right. Special case where the Delaunay triangulation is conforming.

Figure 4 :

 4 Figure 4: Pseudo-code of the alpha hull algorithm.