# goalbased_collective_decisions_axiomatics_and_computational_complexity__006564f6.pdf

Goal-Based Collective Decisions: Axiomatics and Computational Complexity

Arianna Novaro1, Umberto Grandi1, Dominique Longin2, Emiliano Lorini2

1 IRIT, University of Toulouse 2 IRIT, CNRS, Toulouse {arianna.novaro, umberto.grandi, dominique.longin, emiliano.lorini}@irit.fr

We study agents expressing propositional goals over a set of binary issues to reach a collective decision. We adapt properties and rules from the literature on Social Choice Theory to our setting, providing an axiomatic characterisation of a majority rule for goal-based voting. We study the computational complexity of ﬁnding the outcome of our rules (i.e., winner determination), showing that it ranges from Nondeterministic Polynomial Time (NP) to Probabilistic Polynomial Time (PP).

1 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 [Shoham and Leyton-Brown, 2009; Brandt et al., 2016]. In a variety of applications ranging from product conﬁguration 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 [2016]). When facing collective decisions with multiple binary issues, the framework of reference is judgment aggregation (see, e.g., List [2012], Lang and Slavkovik [2014], and Endriss [2016]). A vast literature explores the computational complexity of this framework [Endriss et al., 2012; Baumeister et al., 2015; de Haan and Slavkovik, 2017] and applications range from multiagent argumentation [Awad et al., 2017] to the collective annotation of linguistic corpora [Qing et al., 2014]. However, when considering collective decisionmaking 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 [Klamler and Pferschy, 2007]:

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 [2008] and Dokow and Holzman [2010b], is easily seen to be insufﬁcient in modelling Camille s preference in Example 1. Moreover, the obvious candidate for aggregating propositional goals, logic-based belief merging [Konieczny and P erez, 2002], 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 [2004], we use a simple language of propositional goals to model individual preferences, deﬁning and studying several rules to ﬁnd 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 conﬁgurators, to avoid returning to the users an excessive number of ﬁnal options to choose from. Therefore, our purpose is to deﬁne rules that are as decisive as possible, whilst keeping high standards of fairness as deﬁned 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 [Dokow and Holzman, 2010a; Grandi and Endriss, 2011], and is also true of judgments with abstentions,

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

which correspond to goals speciﬁed 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. [2017]). 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 [Harrenstein et al., 2001] 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 [Dastani and van der Torre, 2002]. 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 goalbased voting, and in Section 5 we conclude.

2 Goal-Based Voting

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

2.1 Basic Deﬁnitions

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 mi(j) = (m1 ij, m0 ij) the number of 1/0 choices of agent i for issue j in the different models of her goal γi, where mx 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 m1(3) = (m1 13, m0 13) = (1, 2). A goal-proﬁle Γ = (γ1, . . . , γn) collects the goals of all agents in N and a goal-based voting rule is a function taking a goal-proﬁle and returning a set of interpretations as the collective outcome. Formally, it is a collection of functions F : (LI)n P({0, 1}m) \ deﬁned 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(Γ) | vj = 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}.

2.2 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 ﬁnd compromises among conﬂicting individual goals. To avoid default options, we introduce the following rule:

Approval(Γ) = arg max v Mod(W

i N γi) |{i N | v Mod(γi)}|.

This rule expresses simple approval voting [Brams and Fishburn, 2007; Laslier and Sanver, 2010]. It is also studied by Lang [2004] as the plurality rule, and in belief merging as an instance of P,d µ -rules by Konieczny and P erez [2002]. 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.

2.3 Issue-Wise Voting We ﬁrst introduce a large class of goal-based rules inspired by the well-known quota rules from judgment aggregation [Dietrich and List, 2007]. 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 deﬁned as follows:

Tr Shµ(Γ)j = 1 iff X

v Mod(γi) v(j) µγi(v)) qj

such that 1 qj n for all j I is the quota of issue j, where for each v Mod(γi) we have µγi(v) = 0 and wi [0, 1] is the individual weight of agent i. To ease notation we omit the vector q = (q1, . . . , qm) from Tr Shµ, 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 ﬂexibility of weights for agents and for models of the individual goals. From here, we can provide a ﬁrst adaptation of the classical issue-wise majority voting for goal-based settings. Inspired by equal and even cumulative voting [Campbell, 1954] we call EQuota rules those Tr Shµ procedures having µγi(v) = 1 |Mod(γi)| and wi = 1 for all v Mod(γi) and for all i N. Thus, the equal and even majority rule EMaj is the EQuota rule having qj = n

2 for all j I. 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:

True Maj(Γ) = Πj IM (Γ)j

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Mod(γ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) True Maj (101) (111) 2s Maj (011) (111)

Table 1: Three goal-proﬁles on which majority-based rules differ.

where for each j I:

( {x} if P i N mx ij |Mod(γi)| > P i N m1 x ij |Mod(γi)| {0, 1} otherwise

Intuitively, True Maj 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 deﬁne a third version of the majority rule as 2s Maj(Γ) = 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 ﬁrst rule on each individual goal, and a second, possibly different, rule on the results obtained in the ﬁrst step. We now prove that the three proposed versions of goalbased majority do not always return the same result.

Proposition 1. There exists goal-proﬁles on which the outcomes of EMaj, True Maj and 2s Maj differ.

Proof sketch. In Table 1 we provide a proﬁle 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 ﬁrst issue, m1 11 |Mod(γ1)| + m1 21 |Mod(γ2)| + m1 31 |Mod(γ3)| = 1+ 2

3 < 2, hence EMaj(Γ1)1 = 0. Take True Maj instead.

Since P i N m1 i1 |Mod(γi)| = 1+ 2

3 = P i N m0 i1 |Mod(γi)| we

get True Maj(Γ1)1 = 1. The calculations for the other cases can be obtained straightforwardly.

3 Axiomatic Analysis

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

3.1 Axiom Deﬁnitions A ﬁrst straightforward generalisation of an axiom from the literature on Social Choice Theory is the following:

Deﬁnition 1. A rule F is anonymous (A) if for any proﬁle Γ 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. Deﬁne ϕ[j 7 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: Deﬁnition 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 7 σ(1), . . . , m 7 σ(m)]. Tr Shµ and EQuota rules are not neutral when the quotas for two issues differ. Neither is Conj v, by permuting issues in a proﬁle of inconsistent goals resulting in a proﬁle 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 True Maj and 2s Maj 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 [List, 2012; Brandt et al., 2016]. First, let Dm = {(a, b) | a, b N and a + b 2m} and C = {{0}, {1}, {0, 1}}. Independence is formally deﬁned as: Deﬁnition 3. A rule F is independent (I) if there are functions f : Dn m C for j I such that for all proﬁles Γ we have F(Γ) = Πj If(m1(j), . . . , mn(j)). Albeit being often identiﬁed as one of the main sources of impossibilities in aggregation theory [List, 2012], we believe that independent (i.e., issue-wise) rules are crucial in solving the tension between fairness and resoluteness in goalbased voting. From the deﬁnitions we easily see that Tr Shµ, EQuota and True Maj are independent, while Conj v and Approval are not since they consider the proﬁle globally. The next axiom holds whenever the unanimous choice of the agents for an issue is respected in the outcome: Deﬁnition 4. A rule F is unanimous (U) if for all proﬁles Γ and for all j I, if mx 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 True Maj and 2s Maj will agree with the proﬁle, interestingly Tr Shµ and EQuota rules do not satisfy it (by setting a high enough quota) as well as Conj v (for a proﬁle where goals are inconsistent and thus the default is chosen). We say that proﬁles Γ 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. Deﬁnition 5. A rule F satisﬁes positive responsiveness (PR) if for all comparable proﬁles Γ = (γ1, . . . , γi, . . . , γn) and Γ = (γ1, . . . , γ i , . . . , γn), for all j I and i N, if mx ij mx 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.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

We conclude by presenting two important fairness axioms. The ﬁrst 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 satisﬁed by all EQuota rules as well as by True Maj: Deﬁnition 6. A rule F is egalitarian (E) if for all Γ, on the proﬁle Γ 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(Γ ). The second axiom instead focuses on possible biases towards acceptance or rejection of the issues. Deﬁnition 7. A rule is dual (D) if for all proﬁles Γ, F(γ1, . . . , γn) = {(1 v(1), . . . , 1 v(m)) | v F(Γ)} where γ = γ[ 1 7 1, . . . , m 7 m]. A similar requirement is called neutrality by May [1952], while in binary aggregation this is known as domainneutrality [Grandi and Endriss, 2011].

3.2 Characterising Goal-Based Majority Rules A seminal result in characterising aggregation rules is May s Theorem [1952], where an axiomatisation of the majority rule in the context of voting over two alternatives is provided. A natural question to ask after deﬁning 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 satisﬁes (E), (I), (N), (A), (PR), (U) and (D) if and only if it is True Maj.

Proof. Right-to-left follows from discussion in Section 3.1. For left-to-right, consider a rule F. Let Γ be an arbitrary proﬁle over n voters and m issues. By (E), we can construct a proﬁle Γ for m issues and n agents, where n is as in Deﬁnition 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 proﬁles over n agents and m issues where agents submit single-model goals. We denote G such a set of proﬁles (hence, in particular, Γ G ). We now show that F(Γ ) = True Maj(Γ ). By (I), there are functions f1, . . . , fm such that F(Γ ) = f1(m1(1), . . . , mn(1)) fm(m1(m), . . . , mn(m)). Observe that since Γ G , we have mi(j) {(0, 1), (1, 0)} for all i N and j I. Hence, we can equivalently see each f on proﬁles in G as a function from {0, 1}n to C. By (N) and (I) we get that f1 = = fm, 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 proﬁle Γ+ G such that for all i N we have m0 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 -proﬁles Γ = Γ0, Γ1, . . . , Γn = Γ+ where exactly one agent i at a step k changes her

goal γi such that m1 ij = 0 in Γk and m1 ij = 1 in Γk+1. By (I) and the deﬁnition 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 proﬁles 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 proﬁle Γℓ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 proﬁles 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 proﬁle Γ where there are exactly q agents accepting j. By (PR) we have F(Γ)j = (0, c). Consider now proﬁle Γ: we have |{i | mi(j) = (0, 1) for γi Γ}| = |{i | mi(j) = (1, 0) for γi Γ}| = q < n+1

2 . Hence, |{i | mi(j) = (0, 1) for γi Γ}| n+1

2 > q. Hence, F(Γ)j = (0, c), contradicting (D). Suppose q > n+1

2 and consider a proﬁle Γ where n+1

2 |{i | mi(j) = (0, 1) for γi Γ}| < q. Then, F(Γ)j = (a, 0) and F(Γ)j = (a, 0), again contradicting (D). To sum up, F is deﬁned 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 P i N mx ij > P i N m1 x ij for x {0, 1}, corresponding to the deﬁnition of True Maj. Since Γ is an arbitrary goal proﬁle, and True Maj satisﬁes (E), we obtained the desired equivalence.

While both EMaj and 2s Maj are based on similar intuitions as True Maj, EMaj has a bias towards the rejection of the issues, while 2s Maj does not satisfy the equality axiom. True Maj 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 grounded if v F(Γ) implies v Mod(γ1 γn). Proposition 2. EQuota, True Maj and 2s Maj are not grounded.

Proof. Consider proﬁle Γ for 3 agents and 3 issues where Mod(γ1) = {(111)}, Mod(γ2) = {(010)} and Mod(γ3) = {(001)}. Both EQuota (with uniform quota 2), True Maj and 2s Maj return (011), contradicting groundedness.

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.

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

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

4.1 Winner Determination We present two deﬁnitions for the winner determination problem, for resolute and irresolute rules, in line with the literature on judgment aggregation [Endriss et al., 2012; Baumeister et al., 2015; de Haan and Slavkovik, 2017]. Note that we provide the existential version of the winner determination problem a universal deﬁnition is also possible [Lang and Slavkovik, 2014]. We start with resolute rules:

WINDET(F) Input: proﬁle Γ, 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: proﬁle Γ, 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 ﬁlling 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(Γ).

4.2 Conjunction and Approval Rules Our ﬁrst complexity result provides a lower bound for the family of conjunction rules Conj v(Γ).

Theorem 2. WINDET (Conj v) is NP-hard.

Proof. We reduce from SAT. Let ϕ [p 1, . . . , p k] be the formula over k variables whose satisﬁability we want to check. Construct an instance of WINDET(Conj v) as follows. Let I = {p 1, . . . , p k} {q}. Consider a proﬁle Γ = (γ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 satisﬁable 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 v |= V i N γi, if the answer is negative it checks v |= V j S ρ(j)=1 j V j S ρ(j )=0 j

(i.e., the formula expressing ρ), excludes the case in which the conjunction of the goals is satisﬁable, but v is not a model. The Approval rule is signiﬁcantly harder. We ﬁrst need some deﬁnitions. Let Θp 2 = PNP[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 [Chen and Toda, 1995]:

MAX-MODEL Input: satisﬁable 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:

Theorem 3. WINDET (Approval) is Θp 2-complete.

Proof. Membership in Θp 2 can be obtained from Proposition 4 by Lang [2004], using the following formula in the deﬁnition of the ELECT-SAT problem:

j S ρ(j )=0

For completeness, we give a reduction from MAXMODEL. Consider an instance of MAX-MODEL where ϕ[p1, . . . , pm] is a satisﬁable formula and pi 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 proﬁle such that γ1 = = γm+1 = ϕ and γm+2 = p1, . . . , γ2m+1 = pm. 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 ﬁrst 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. Speciﬁcally, the support of v is (m + 1) + |{pi | v(pi) = 1}|. Hence, only those v Mod(ϕ) with a maximal number of 1s are in the outcome of Approval(Γ). It now sufﬁces to set S = {pi} for pi the propositional variable in the instance of MAX-MODEL and ρ(pi) = 1. Therefore, a formula ϕ has a model with a maximal number of variables set to true where pi is true if and only if WINDET (Approval) returns yes on the constructed input.

4.3 Threshold Rules We study the complexity of ﬁnding the outcome of Tr Shµ

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 P 1 i ℓ|Mod(ψi)| > k?

We now ﬁnd the complexity for k MODELSUM.

Lemma 1. k MODELSUM is NP-complete.

Proof. To show membership in NP guess k1, . . . , kℓnumbers with ki k + 1 for all 1 i ℓ, and guess X1, . . . , Xℓ sets, where Xi 2|Var| for 1 i ℓand Var is the set of variables of ψ1, . . . , ψℓ. The size of each Xi for 1 i ℓ is bounded by k + 1, and each Xi corresponds to a set of models. It is then easy to check that k1 + + kℓ> k, that for all 1 i ℓwe have |Xi| = ki and for all vi Xi we have vi Mod(ψi). For completeness, we reduce from SAT. Let ϕ be the formula whose satisﬁability we want to check. Construct now an instance of k MODELSUM where ψ1 = ϕ and k = 1. Formula ϕ is satisﬁable 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 Tr Shµ.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Theorem 4. For µγi(v) = 1 constant and wi = 1 for all i N, WINDET(Tr Shµ) is NP-complete.

Proof. For membership in NP consider a proﬁle Γ = (γ1, . . . , γn) and an issue j. Guess k1, . . . , kn numbers with ki k+1 for 1 i n, and guess X1, . . . , Xn sets of models where Xi 2m and for each v Xi we have v(j) = 1 for i N. It is then easy to check whether k1+ +kn > qj, that for all i N we have |Xi| = ki and for all vi Xi we have vi 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(Tr Shµ) 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 qj = 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 Tr Shµ(Γ)p = 1.

While it would be easy to adapt this proof to deal with different values for the individual weights wi (to be multiplied with the ki 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 difﬁcult problem.

4.4 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 nondeterministic 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 [Papadimitriou, 2003]. Consider the following problem:

MAJ-SAT-p Input: propositional formula ϕ, variable p of ϕ Question: Is it the case that |Mod(ϕ p)| > |Mod(ϕ p)|?

We ﬁrst 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 True Maj we study a (strict) resolute version True Maj r. Theorem 5. WINDET(2s Maj), WINDET(EMaj) and WINDET(True Maj r) are PP-hard.

Proof. The proof is analogous for the three rules, so we only prove it for 2s Maj. We reduce from MAJ-SAT-p. Consider the formula ϕ and the variable p of ϕ as our instance of MAJSAT-p. Consider now a proﬁle Γ for a single agent such that γ1 = ϕ. Since we are dealing with resolute rules, we simply have to ﬁx 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 2s Maj(Γ)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 2s Maj(Γ)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 True Maj 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.

5 Conclusions and Future Work Starting from the observation that classical judgment aggregation falls short in many examples of collective decisionmaking in multi-issue domains, such as creating a shared travel plan or collective product conﬁguration, 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 (True Maj). 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.

Acknowledgments We are grateful to the AAMAS and IJCAI reviewers, as well as to J erˆome 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-LABX0040-CIMI within the program ANR-11-IDEX-0002-02.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

References [Awad et al., 2017] Edmond Awad, Richard Booth, Fernando Tohm e, and Iyad Rahwan. Judgement aggregation in multi-agent argumentation. Journal of Logic and Computation, 27(1):227 259, 2017. [Baumeister et al., 2015] Dorothea Baumeister, G abor Erd elyi, Olivia Johanna Erd elyi, and J org Rothe. Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules. Mathematical Social Sciences, 76:19 30, 2015. [Brams and Fishburn, 2007] Steven Brams and Peter C. Fishburn. Approval voting. Springer Science & Business Media, 2007. [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D Procaccia, and J erˆome Lang. Handbook of Computational Social Choice. Cambridge University Press, 2016. [Campbell, 1954] Whitney Campbell. The origin and growth of cumulative voting for directors. The Business Lawyer, 10(3):3 16, 1954. [Chen and Toda, 1995] Z.Z. Chen and S. Toda. The complexity of selecting maximal solutions. Information and Computation, 119(2):231 239, 1995. [Dastani and van der Torre, 2002] Mehdi Dastani and Leendert van der Torre. Specifying the merging of desires into goals in the context of beliefs. In Proceedings of the 1st Eur Asian Conference on Information and Communication Technology (ICT-Eur Asia), 2002. [de Haan and Slavkovik, 2017] Ronald de Haan and Marija Slavkovik. Complexity results for aggregating judgments using scoring or distance-based procedures. In Proceedings of the 16th Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 2017. [Dietrich and List, 2007] Franz Dietrich and Christian List. Judgment aggregation by quota rules: Majority voting generalized. Journal of Theoretical Politics, 19(4):391 424, 2007. [Dietrich and List, 2008] Franz Dietrich and Christian List. Judgment aggregation without full rationality. Social Choice and Welfare, 31(1):15 39, 2008. [Dokow and Holzman, 2010a] Elad Dokow and Ron Holzman. Aggregation of binary evaluations. Journal of Economic Theory, 145(2):495 511, 2010. [Dokow and Holzman, 2010b] Elad Dokow and Ron Holzman. Aggregation of binary evaluations with abstentions. Journal of Economic Theory, 145(2):544 561, 2010. [Elkind et al., 2017] Edith Elkind, Martin Lackner, and Dominik Peters. Structured preferences. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 10, pages 187 207. AI Access, 2017. [Endriss et al., 2012] Ulle Endriss, Umberto Grandi, and Daniele Porello. Complexity of judgment aggregation. Journal of Artiﬁcial Intelligence Research, 45:481 514, 2012.

[Endriss, 2016] Ulle Endriss. Judgment aggregation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 17, pages 399 426. Cambridge University Press, 2016. [Grandi and Endriss, 2011] Umberto Grandi and Ulle Endriss. Binary aggregation with integrity constraints. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI), 2011. [Harrenstein et al., 2001] Paul Harrenstein, Wiebe van der Hoek, John-Jules Meyer, and Cees Witteveen. Boolean games. In Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 2001. [Klamler and Pferschy, 2007] Christian Klamler and Ulrich Pferschy. The traveling group problem. Social Choice and Welfare, 29(3):429 452, 2007. [Konieczny and P erez, 2002] S ebastien Konieczny and Ram on Pino P erez. Merging information under constraints: A logical framework. Journal of Logic and Computation, 12(5):773 808, 2002. [Lang and Slavkovik, 2014] J erˆome Lang and Marija Slavkovik. How hard is it to compute majority-preserving judgment aggregation rules? In Proceedings of the 21st European Conference on Artiﬁcial Intelligence (ECAI), 2014. [Lang and Xia, 2016] J erˆome Lang and Lirong Xia. Voting in combinatorial domains. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel Procaccia, editors, Handbook of Computational Social Choice, chapter 9, pages 197 222. Cambridge University Press, 2016. [Lang, 2004] J erˆome Lang. Logical preference representation and combinatorial vote. Annals of Mathematics and Artiﬁcial Intelligence, 42(1-3):37 71, 2004. [Laslier and Sanver, 2010] Jean-Franc ois Laslier and Remzi M. Sanver. Handbook on Approval Voting. Springer Science & Business Media, 2010. [List, 2012] Christian List. The theory of judgment aggregation: an introductory review. Synthese, 187(1):179 207, Jul 2012. [May, 1952] Kenneth O. May. A set of independent necessary and sufﬁcient conditions for simple majority decision. Econometrica: Journal of the Econometric Society, pages 680 684, 1952. [Papadimitriou, 2003] Christos H. Papadimitriou. Computational Complexity. John Wiley and Sons Ltd., 2003. [Qing et al., 2014] Ciyang Qing, Ulle Endriss, Raquel Fern andez, and Justin Kruger. Empirical analysis of aggregation methods for collective annotation. In Proceedings of the 25th International Conference on Computational Linguistics (COLING), 2014. [Shoham and Leyton-Brown, 2009] Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)