Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability

1 Introduction

In a number of application domains, including (some forms of) fair division, voting, or the choice of a common set of items, a decision has to be made by a group of individuals by aggregating their preferences over the available alternatives. In fact, a drastic division exists between ordinal settings, where agents express preference relations over alternatives, and cardinal settings, where they express utility functions mapping the alternatives to some suitable (typically numerical) scale. In the paper, we focus on the latter settings, and our pragmatic goal is therefore to aggregate such cardinal preferences into a collective utility function.

Now, in group decision-making, the set of possible solutions has often a combinatorial structure: possible allocations of items to agents, coalition structures among agents, binary vectors in multiple referenda, subsets of k candidates in committee elections, etc. The exponential size of the set of solutions implies a tension between expressivity (allowing the agents to express any possible utility function) and elicitation and computation complexity (avoiding the agents to spend hours specifying their preferences, and the computer to spend hours computing the optimal solution).

One common way that sacrifices expressivity but makes elicitation (and often computation) easy consists in assuming that utility functions are additive, that is, described only by their values on singletons, the utility of a tuple of values being

J´erˆome Lang

Universit´e Paris-Dauphine, France lang@lamsade.dauphine.fr

then the sum of utilities of the individual values. For instance, when expressing utilities over sets of goods, the utility value given by an agent to a set of goods is the sum of all values she gives to the individual goods in the set. However, assuming additivity implies a huge loss of expressivity, because it does not allow the agents to express preferential dependencies. On the other hand, allowing agents to express arbitrary utility functions over a combinatorial set of solutions by listing all solutions together with their utility is clearly unpractical, because it would amount to ask each agent to provide an exponentially large list of values.

A way of reconciliating expressivity and complexity is to use a compact representation language for representing utility functions. Weighted propositional logic is a language of this kind that attracted much attention in the literature: Each individual expresses her preferences as a set of propositional formulas associated with numerical values. Given an interpretation σ assigning a truth value to each variable, the utility of the individual is defined as the sum 1 of the values associated with the formulas satisfied by σ. Moreover, in order to preserve the semantics of the application, interpretations might be restricted to those satisfying some given constraints.

Example 1.1. Consider an allocation problem with agents a1 and a2, and three indivisible goods g1, g2, g3. The setting can be modeled via the set of Boolean variables V = {Xi,j | i ∈ {1, 2}, j ∈ {1, 2, 3}}. An interpretation σ over V is naturally associated with an allocation, where Xi,j true in σ means that ai receives good gj . We focus on those interpretations satisfying the formula ∧j ∧i̸=i′ ¬(Xi,j ∧Xi′ ,j), which constrains each good to be allocated at most to one individual.

Assume a1 chooses to express her utility function by the set of weighted formulas {〈X1,1 ∨ (X1,2 ∧X1,3), 3〉, 〈X1,1 ∧ X1,2, 2〉}, while a2 has additive preferences, expressed by the set {〈X2,1, 2〉, 〈X2,2, 1〉}, 〈X2,3, 2〉}. Let π be the allocation giving {g1, g2} to a1 and {g3} to a2. The interpretation corresponding to π is σπ where the variables evaluating to true are those in {X1,1,X1,2,X2,3}. The utility of a1 (resp., a2) in π is given by u1(σπ) = 3 + 2 = 5 (resp., u2(σπ) = 2.) ◁

Expressing utilities by weighted formulas is more succinct than expressing them directly, and is fully expressive, in the sense that every utility function can be expressed by some set of weighted formulas. Detailed results on the expressivity, succinctness and complexity of various fragments of this language are in [Uckelman et al., 2009]. The succinctness of weighted formulas with respect to other logical representation languages is also discussed in [Coste-Marquis et al., 2004]. Weighted formulas have also been used to express values of coalitions in cooperative games and hedonic games, in socalled marginal contribution nets [Ieong and Shoham, 2005; Elkind et al., 2009; Elkind and Wooldridge, 2009], as well as in fair division [Bouveret and Lang, 2008]. Moreover, related languages have been designed for bidding in combinatorial auctions [Boutilier and Hoos, 2001; Nisan, 2006].

1 See [Uckelman and Endriss, 2010] for an alternative approach where the utility is defined as the maximum over the values of the satisfied formulas, and [Lafage and Lang, 2000] for a discussion on (further) possible aggregation functions.

Note that, although preference aggregation over combinatorial structures has received a lot of attention these last years, many approaches focus on voting, where preferences are ordinal (see [Lang and Xia, 2015] for a survey); and among general approaches that deal with cardinal preferences, most of them deal with specific application domains (the closest to our work being [Escoffier et al., 2013]). There are very few existing general (domain-independent) languages allowing for expressing and aggregating cardinal preference. In particular, GAI networks, highly related to weighted formulas, have been used by [Gonzales et al., 2008] for expressing group decision making and searching for Pareto-optimal solutions. Logic-based preference representation of collective decision problems has been dealt with in a few papers only [Lafage and Lang, 2000; Uckelman and Endriss, 2010] (see [Endriss, 2011] for a discussion); the main difference with our work is that we address fair optimization in a generic way, and investigate its complexity in depth.

In the paper, we adopt the language of weighted formulas to express individual preferences, and we focus on how these preferences can be aggregated: In the classical utilitarian setting, the collective utility (or utilitarian social welfare) is the sum of the utilities of the individuals. In fair group decisionmaking, instead, it is more appropriate to consider egalitarian (or Rawlsian) social welfare, which is the utility of the least satisfied agent. For instance, under egalitarianism, finding an optimal allocation of indivisible goods to agents is the so-called Santa Claus problem [Bezakova and Dani, 2005; Bansal and Sviridenko, 2006].

Example 1.1, continued. The utilitarian social welfare of π is 5 + 2 = 7. In fact, π is the allocation maximizing the utilitarian social welfare. However, the egalitarian social welfare of π is 2, while the allocation π′ giving g1 to a1 and {g2, g3} to a2 is fairer: its egalitarian social welfare is 3. ◁

Weighted propositional logic can be used in a wide range of collective optimization problems. However, this setting has not been put systematically under the computational lens. In particular, the complexity of the most relevant reasoning problems arising therein and the identification of islands of tractability (cf. [Bordeaux et al., 2014; Greco and Scarcello, 2013]), i.e., of classes of instances for which solutions can be efficiently computed, have been unexplored.

The goal of the paper is to fill this gap, by depicting a clear picture of the complexity of collective decision making with weighted formulas under egalitarianism and by contrasting it with results that hold under utilitarianism. In Section 2, we show that weighted formulas can serve as a general compact representation language for various multiagent optimization problems. In Section 3, we analyze the complexity of deciding the existence of an interpretation guaranteeing some given utilitarian or egalitarian social welfare, and of deciding whether some given interpretation is optimal. In Section 4, starting from the observation that optimal interpretations can be unlikely computed in polynomial time, we define the frontier of tractability by considering all possible combinations for the following restrictions: syntactical restrictions on the propositional language, allowed weights, number of individuals, number of weighted formulas per individual, and maximum number of variables in each formula. In Section 5 and Section 6, the frontier is then charted for the utilitarian and egalitarian social welfare, respectively. Avenues for further research are discussed in Section 7.

2 Formal Framework

Goalbases

Throughout the paper, we assume that a universe V of variables is given, and that the propositional language P consists of all formulas built over V by using the Boolean connectives ∧, ∨, and ¬, plus the constants ⊤ (true) and ⊥ (false). For any propositional formula ϕ ∈ P, dom(ϕ) denotes the domain of ϕ, i.e., the set of all the variables occurring in it. An interpretation σ : W → {⊤,⊥} over W ⊆ V is a function assigning a Boolean value to each variable in W. If ϕ ∈ P with W ⊇ dom(ϕ), then σ |= ϕ means that the interpretation σ is a model of ϕ. A formulas ϕ is satisfiable if it has a model.

A weighted formula is a pair 〈ϕ,w〉, where ϕ ∈ P is a propositional formula and where w ∈ Q is a rational number. A goalbase G is a finite set of weighted formulas, whose domain is dom(G) = ⋃〈ϕ,w〉∈G dom(ϕ). For any interpretation σ over a superset of dom(G), the number G(σ) = ∑〈ϕ,w〉∈G such that σ|=ϕ w is the value of σ w.r.t. G.

For any set W of variables, we denote by I(W) the set of all interpretations that can be defined over W.

A utility function over W is a mapping u : I(W) → Q. Given the function u, we can always build a goalbase Gu with dom(Gu) = W and such that Gu(σ) = u(σ), for each σ ∈ I(W) [Coste-Marquis et al., 2004; Uckelman et al., 2009].

Utilitarian and Egalitarian Social Welfare

Let G be a set of goalbases, and let dom(G) = ⋃G∈G dom(G) denote the domain of G. Each goalbase G ∈ G represents a utility function over I(W), and we look to define suitable ways to aggregate all these functions into a collective utility function over I(W). Moreover, the aggregation process is often subject to constraints emerging from the application, which can be naturally modeled (again) as formulas in P that have to be satisfied by the candidate interpretations.

Definition 2.1. A (group decision-making) scenario is a pair (G, Γ) where G is a set of goalbases and Γ (the constraint) is a satisfiable propositional formula in P. An interpretation σ ∈ I(dom(G)) is feasible (in (G, Γ)) if σ |= Γ. □

For instance, in Example 1.1, the fact that each good can be allocated at most to one individual is encoded via the constraint Γ = ∧j ∧i̸=i′ ¬(Xi,j ∧Xi′ ,j). Therefore, the pair ({G1,G2}, Γ) where G1 and G2 are the goalbases of agents a1 and a2, respectively, is a group decision-making scenario formalizing the allocation problem introduced there.

A scenario (G, Γ) is positive (resp., negative) if every weighted formula occurring in the goalbases in G is associated with a positive (resp., negative) weight-w.l.o.g., weighted formulas of the form 〈ϕ, 0〉 can be removed.

Let σ be any feasible interpretation in I(dom(G)). Then, the utilitarian social welfare of σ is the value SW(σ) = ∑G∈G G(σ). We say that σ is SW-optimal if it has the maximum utilitarian social welfare over all feasible interpretations in I(dom(G)). The set of all SW-optimal interpretations is denoted by SW∗-INT(G, Γ), and their utilitarian social welfare is denoted by SW∗-VAL(G, Γ).

Now, the intuition in the exposition that follows is to look for interpretations that are not "too far" from the optimum values that can be achieved when optimizing each of the goalbases independently on the others. The definition below uses a normalization mechanism to uniformly deal with utilities defined over different scales. We will see that, whenever preferences are already normalized, as it is often assumed in fair optimization (see, e.g., [Escoffier et al., 2013]), the definition reduces to a classical max-min fairness criterion.

Definition 2.2. Let (G, Γ) be a group decision-making scenario, let α ∈ Q, and let σ be a feasible interpretation. We say that σ is α-fair (in (G, Γ)) if, for each G ∈ G,

where MIN(G, Γ) denotes the minimum value G(σ′ ) achieves over all possible feasible interpretations σ′ . □

Note that every feasible interpretation σ is 0-fair. Then, the egalitarian value of σ, denoted by EG(σ), is the maximum value α for which σ is α-fair. Equivalently,

Note that EG(σ) ≤ 1. In particular, if EG(σ) = 1, then σ is an interpretation over which every goalbase can achieve its optimal value. We say that σ is EG-optimal if it has the maximum egalitarian value over all possible feasible interpretations. The set of all EG-optimal interpretations is denoted by EG∗-INT(G, Γ), and EG∗-VAL(G, Γ) is their egalitarian value.

Example 1.1, continued. Each agent can get all objects if she were alone; hence, SW∗-VAL({G1})=SW∗-VAL({G2})=5. Moreover, MIN(G1, Γ)=MIN(G2, Γ)=0. Thus, an interpretation σ is α-fair if, and only if, G1(σ)≥α×5 and G2(σ)≥α×5. Accordingly, the interpretation σπ′ , where the variables evaluating to true are those in {X1,1,X2,2,X2,3}, is such that EG(σπ′ )=min{ 3 5 , 35 }= 35 . Note that σπ′ is EG-optimal, and we have EG∗-VAL({G1, G2}, Γ)= 35 . ◁

Examples (in the Egalitarian Setting)

Weighted formulas are easily seen to apply in the utilitarian setting (cf. [Uckelman et al., 2009]). We next show that they apply to several problems in the egalitarian setting, too.

For the sake of exposition, we shall use the propositional language extended by cardinality formulas. In particular, the formula ≥ k : ϕ1, . . . , ϕp is satisfied by an interpretation σ if |{ϕi | i ∈ {1, . . . , p}, σ |= ϕi}| ≥ k holds-similarly for ≤ k : ϕ1, . . . , ϕp and for = k : ϕ1, . . . , ϕp. 2

Fair division of indivisible goods. As we have seen in Example 1.1, fair division of indivisible goods can be naturally expressed in our general framework. Variations of the problem involving, for instance, complex constraints over allocations (such as when some goods can be assigned to more than one agent and some not, etc.) can be expressed as well.

Minimax approval voting (e.g., [Brams et al., 2007]): We have to build a committee of exactly k persons among m candidates from the set K = {P1, . . . , Pm}. Each of n voters approves a subset Ai ⊆ K. A set C ⊆ K, with |C| = k, is a minimax approval committee if it minimizes the value maxi |C \Ai ∪Ai \C|. The problem can be modeled as a scenario ({G1, . . . , Gn}, Γ), where candidates in {P1, . . . , Pm} are viewed as variables. Intuitively, for any interpretation σ, σ(Pj) = ⊤ (resp., ⊥) means that Pj is included (resp., not included) in the committee. The scenario is such that for each voter i, Gi = {〈Pj, 1〉|Pj ∈ Ai}∪{〈¬Pj, 1〉|Pj /∈ Ai}, and Γ is =k:P1, . . . , Pm. So, interpretations σ maximizing EG(σ) one-to-one correspond to minimax approval committees.

Multifacility location (e.g., [Elzinga et al., 1976]): Let L = {L1, . . . , Lm} be a set of locations, and let ui(Lj) be the reward for agent i when using a facility located in Lj . We want to open at most k facilities, and each agent will use the one providing the best reward to her. The problem can be modeled as a scenario ({G1, . . . , Gn}, Γ) defined over the variables in L. For any interpretation σ, σ(Lj) = ⊤ (resp., σ(Lj) = ⊥) means that a facility is opened (resp., not opened) at location Lj . For each agent ai, let us first order the locations according to their nonincreasing order of ui: ui(Li1 ) ≥ . . . ≥ ui(Lim ), with {i1, . . . , im} = {1, . . . ,m}. Then, we define:

Hence, Gi(σ) is the best reward of agent ai derived from using any of the facilities that are opened (according to σ). Finally, Γ is the constraint ≤ k : L1, . . . ,Lm. Note that EG-optimal interpretations one-to-one correspond to solutions where facilities are opened as to maximize the (normalized) reward of the least satisfied agent. Similar problems where each agent enjoys the best item in the selected subset are budgeted social choice [Lu and Boutilier, 2011] and full proportional representation [Chamberlin and Courant, 1983; Monroe, 1995; Procaccia et al., 2008; Betzler et al., 2013; Skowron et al., 2013].

Fair group knapsack (e.g., [Shachnai and Tamir, 2001]): The setting is similar to fair division of indivisible goods, except the constraint no longer prescribing that goods are nonsharable, but rather enforcing a bound on the number (or volume) of goods that can be put in the knapsack.

2 Cardinality formulas can be rewritten in standard propositional logic, by introducing additional variables but without an exponential blow-up in their size [van Hentenryck and Deville, 1991].

3 Maximizing Social Welfare

Given X ∈ {SW, EG} and a scenario (G, Γ) provided as input, we focus on the following two decision problems:

X-VAL-CHECK: Given γ ∈ Q, does X∗-VAL(G, Γ) ≥ γ hold? X-INT-CHECK: Given σ∈I(V), does σ∈X∗-INT(G, Γ) hold?

We start with the utilitarian social welfare, where intractability is established over single-agent scenarios (G, Γ), i.e., with |G| = 1, and without constraints (i.e., Γ = ⊤).

Theorem 3.1. SW-VAL-CHECK (resp., SW-INT-CHECK) is NPcomplete (resp., co-NP-complete). Hardness holds on positive and negative single-agent scenarios without constraints.

Moving to the egalitarian social welfare, we have to observe that according to Definition 2.2, even just checking whether some given interpretation is α-fair requires the computation of the maximum utilitarian social welfare associated with each of the individual goalbases. We show below that this problem is F∆P2 -hard. For completeness, recall that F∆P2 (resp., ∆P2 ) is the set of all computation (decision) problems solvable in polynomial time by using a NP oracle whose cost is assumed to be unitary-see, e.g., [Papadimitriou, 2003].

Proposition 3.2. Computing the maximum utilitarian social welfare is F∆P2 -hard, even in single agent scenarios.

Proof Sketch. Consider the ∆P2 -complete problem MAXASG-ODD [Wagner, 1987]: given a satisfiable formula Σ over {X1, . . . ,Xn}, does Xn evaluates to true in the lexicographically greatest model (w.r.t. the order {X1 > · · · > Xn})? The result follows by building in polynomial time ({G},Σ), where G = {〈X1, 2n-1 〉, . . . , 〈Xn, 20 〉}. □

The result implies that normalization in Definition 2.2 typically determines a complexity increase. Take for instance the problem EG-VAL-CHECK. Without normalization, the problem is NP-complete (membership in NP is clear, since it suffices to guess an interpretation σ and check that Gi(σ) ≥ γ, for each i). However, with normalization, it climbs up to ∆P2 .

Theorem 3.3. Given a rational number γ, checking whether EG∗-VAL(G, Γ) ≥ γ holds is ∆P2 -complete.

To circumvent the issue, we shall hereinafter reason on scenarios where values are explicitly normalized. Formally, a scenario (G, Γ) is normalized if SW∗-VAL({G}, Γ)=1 and MIN(G, Γ)=0, for each G ∈ G. Over normalized scenarios (G, Γ), fair optimization reduces to a max-min approach:

Note that any scenario (G, Γ) can be transformed into an equivalent normalized one ( ˆ G, Γ) by removing from G all goalbases G′ such that SW∗-VAL({G′}, Γ) - MIN(G′ , Γ)=0, and by replacing each remaining goalbase G with the modified goalbase containing, for each 〈ϕ, c〉 ∈ G, the two weighted formulas 〈ϕ, c/H〉 and 〈⊤,-MIN(G, Γ)/H〉, where H = SW∗-VAL({G}, Γ) - MIN(G, Γ). In fact, to constructively apply the normalization procedure, a bottleneck to be faced is the computation of the utilitarian social welfare. That is, the source of complexity underlying the ∆P2 -hardness in Theorem 3.3 is now made "explicit" in this pre-processing phase. Note that if ˆ G = ∅, then any feasible interpretation for (G, Γ) is trivially EG-optimal. Otherwise, the equivalence of (G, Γ) and ( ˆ G, Γ) is stated below-the proof is simple.

Proposition 3.4. If ˆ G̸=∅, then EG∗-VAL( ˆ G, Γ)=EG∗-VAL(G, Γ), EG∗-INT( ˆ G, Γ)=EG∗-INT(G, Γ), and ( ˆ G, Γ) is normalized.

In the following, we assume that any scenario (G, Γ) provided as input to problems under egalitarianism is normalized, and that G is non-trivial (i.e., |G| > 1, for otherwise egalitarianism is immaterial). The counterpart of Theorem 3.1 is stated below.

Theorem 3.5. EG-VAL-CHECK (resp., EG-INT-CHECK) is NP-complete (resp., co-NP-complete).

We leave the section by noticing that after normalization, complexity results derived for utilitarianism and for egalitarianism coincide-see Figure 1. In fact, under egalitarianism (over normalized scenarios), "negative" scenarios are not possible and arbitrary scenarios coincide with "positive" ones.

4 Charting the Frontier of Tractability

The results derived so far suggest that the problems of interest are unlikely to be solvable in polynomial time, even by considering restrictions on the weights associated with the various formulas. This motivates to identify islands of tractability by considering further restrictions, which we do now.

We start by defining different restrictions on formulas and weights. Consider the language L{∧,∨,¬} consisting of all propositional formulas ϕ built according to the following grammar: ϕ ::= X | ¬X | (ϕ ∧ · · · ∧ ϕ) | (ϕ ∨ · · · ∨ ϕ), where X is any variable in V. If C ⊆ {∧, ∨, ¬} is a set of Boolean connectives, then we write LC to denote the set of all the formulas in L{∧,∨,¬} that do not contain symbols in C \ {∧, ∨, ¬}. Note that we assume that all formulas are in Negation Normal Form, that is, that negation applies only over variables (if it could apply over general subformulas, then ∧ would be expressible from ∨ and vice versa).

Let h1, h2, h3 ∈ {1, c,∞}, let S ⊆ {+,-} with |S|≥1, and let GBC,S[h1, h2, h3] be the set of scenarios (G, Γ) where:

• Γ as well as all formulas in G are taken from LC;
• if S = {+} (resp., S = {-}), then (G, Γ) is positive (resp., negative); if S = {+,-} then no restriction is imposed on the weights associated with the formulas;
• if h1 = 1 (resp., h1 = c), then |G| = 1 (resp., |G| is bounded by a fixed constant); if h1 = ∞, then no bound is required over |G|;
• if h2 = 1 (resp., h2 = c), then |Gi| = 1 (resp., |Gi| is bounded by a fixed constant), for each Gi ∈ G; if h2 =∞, then no bound is required over any |Gi|; and

• if h3 = 1 (resp., h3 = c), then |dom(ϕi)| = |dom(Γ)| are equal to 1 (resp., are bounded by a fixed constant) for each Gi ∈ G and for 〈ϕi, wi〉 ∈ Gi; if h3 = ∞, then no bound is required over |dom(ϕi)| and |dom(Γ)|.

The basic computational task we shall consider is the problem of computing an X-optimal interpretation restricted on GBC,S[h1, h2, h3], which is hereinafter denoted as XFINDC,S[h1, h2, h3]. 3 To analyze its complexity, we define a concept of frontier of tractability, which allows us to express more succinctly our results, by avoiding to get lost in the very large number of different combinations we shall consider.

Definition 4.1. The frontier of tractability of X ∈ {SW, EG} w.r.t. h1, h2, h3 ∈ {1, c,∞}, denoted by X-FrT[h1, h2, h3], is the minimal set of pairs (C, S) with C ⊆ {∨, ∧, ¬} and ∅ ⊂ S ⊆ {+, -} such that:

• ∀(C, S)∈X-FrT[h1, h2, h3], X-FINDC,S[h1, h2, h3] is in P;
• ∀(C′ , S′ ) with C ′ ⊆ {∧, ∨, ¬} and S′ ⊆ {+, -} such that there is no pair (C, S) ∈ X-FrT[h1, h2, h3] with C∪S ⊇ C ′ ∪ S′ , X-FINDC,S[h1, h2, h3] is NP-hard. □

Note that the notion precisely captures the intuition that the given pairs mark the boundary between tractable and intractable settings. The following two sections are then devoted to present the frontier of tractability for the utilitarian and egalitarian social welfare, respectively.

5 Results for Utilitarian Social Welfare

We start the analysis with the case h1 = 1, which is the classical setting of individual decision-making. The use of goalbases has been largely explored in this case, but the frontier of tractability has not been charted according to the various qualitative parameters we are considering.

Theorem 5.1. Results for individual optimization are summarized in Figure 2.

Note that the frontier emerged to be rather fragmented. This needed to establish a large number of NP-hardness and tractability results in order to chart it. Since we cannot report all proofs here, we focus below on discussing two scenarios that are representative of the techniques we have adopted. First, we consider a tractable class.

3 If X-FINDC,S[h1, h2, h3] is in P, then we can answer X-VALCHECK and X-INT-CHECK in polynomial time, too.

Proof. Let (G, Γ) be in GB{∧,∨},{+}[1,∞, c], and observe that the constraint Γ contains a constant number of variables only. So, we can proceed as follows. First, we can explicitly enumerate all possible assignments σΓ for these variables. For each assignment σΓ such that σΓ |= Γ, we can solve the scenario (G[σΓ],⊤), where G[σΓ] is derived from G by just replacing each variable in the domain of σΓ with ⊤ or ⊥ depending on its truth value in σΓ. Eventually, over all SW-optimal interpretations computed over the scenarios of this kind, we return the one with the maximum associated possible SW-value. In fact, all rules in (G[σΓ],⊤) are positive and negation is not allowed. Thus, an optimal interpretation for (G[σΓ],⊤) is one where all variables are mapped to true (see Theorem 5.6 in [Uckelman et al., 2009]). □

The proof for an intractable scenario is now illustrated.

Lemma 2. SW-FIND{∨,¬},{-}[1,∞, c] is in NP-hard.

Proof. Let I = {I1, . . . , In} be a collection of items, and S = {S1, . . . , Sm} a set of subsets of I. An exact cover (over I and S) is a set S ′ ⊆ S such that Ii belongs to exactly one element of S ′ for all i ∈ {1, . . . , n}. Deciding whether there is an exact cover is known to be NP-hard, even if |Sj| = 3 holds for each j ∈ {1, . . . ,m}, and if each element Ii, with i ∈ {1, . . . , n}, belongs precisely to three different sets in S. Given I and S, we build the goalbase G = G1 ∪ · · · ∪ Gn, where each set Gi is defined as follows. Elements in S are transparently viewed as variables. For each item Ii ∈ I, if Si1 , Si2 , and Si3 are the sets where Ii occurs, then define Gi = {〈¬Sik ∨Sih ∨Sif , -1〉 | h, k, f ∈ {1, 2, 3} with h ̸= k, h ̸= f, f ̸= k}. Let σ be any interpretation over {Si1 , Si2 , Si3 }. Observe that Gi(σ) = -4 (resp., Gi(σ) = -6) if, and only if, exactly one of the variables in the domain evaluates true (resp., either none of the variables or more than one variable evaluate true). Therefore, there is an exact cover if, and only if, SW∗-VAL({G}) = -4×n. □

Moving from h1 = 1 to h1 ∈ {c,∞}, we just observe that the optimization of a set G of goalbases is equivalent to the optimization of G = {〈ϕ,w〉 | ∃Gi ∈ G such that 〈ϕ,w〉 ∈ Gi}. Thus, the following can be established.

Corollary 5.2. For each h3 ∈ {1, c,∞}, it holds that

1. SW-FrT[c, 1, h3] = SW-FrT[c, c, h3] = SW-FrT[1, c, h3];
2. SW-FrT[c,∞, h3] = SW-FrT[1,∞, h3]; and
3. SW-FrT[∞, h2, h3] = SW-FrT[1,∞, h3], h2 ∈ {1, c,∞}.

6 Results for Egalitarian Social Welfare

We now focus on the egalitarian social welfare.

Theorem 6.1. Results for the egalitarian social welfare are summarized in Figure 2.

Recall that, under egalitarianism, we assume that scenarios are given which are normalized and non-trivial. Accordingly, the classes GB{∧,∨,¬},{-}[h1, h2, h3] are considered as (trivially) tractable, for notational uniformity. For the remaining classes in Figure 2, we discuss representative cases. We start with the proof for a tractability frontier with h2 = ∞.

Proof Sketch. We observe that whenever C = {∧, ∨} and (G, Γ) is positive, then the interpretation mapping all variables to true is in EG∗-VAL(G, Γ). It remains to focus on the class GBC,S[c,∞, 1], by distinguishing two cases.

(1) C ⊇ {¬} and S = {+}. We show that the setting is NP-hard with a reduction from the well-known PARTITION problem: given a multiset S = {s1, s2, . . . , sn} of natural numbers, is there a partition of S into two multisets S1 and S2 such ∑p∈S1 p = ∑q∈S2 q? Indeed, given this instance, we can consider two goalbases G1 and G2 built over the variables {X1, . . . ,Xn} and such that G1 = ⋃si∈S {〈Xi, siM 〉} and G2 = ⋃si∈S {〈¬Xi, siM 〉}, with M = ∑si∈S si. Note that SW∗-VAL({G1},⊤) = SW∗-VAL({G2},⊤) = 1. Moreover, ({G1,G2},⊤) is normalized, and EG∗-VAL({G1,G2},⊤) = 12 if, and only if, S is a positive instance of PARTITION.

(2) C ⊇ {} and S = {+,-}. We exhibit another reduction from PARTITION. Indeed, let us build the setting with the two goalbases G′1 = ⋃si∈S {〈Xi, siM 〉} and G′2 = ⋃si∈S {〈Xi,- siM 〉} ∪ {〈⊤, 1〉}. The scenario ({G′1 ,G′2},⊤) is normalized, and it can be again checked that EG∗-VAL({G′1 ,G′2 },⊤) = 12 if, and only if, S is a positive instance of PARTITION. □

Note that the island of tractability identified in the above result is rather small. Good news comes instead for h2 = c.

Proof Sketch. (Tractability Results) Observe that for the class GB{∧,∨},{+}[c, c,∞], the interpretation mapping all variables to true is optimal. Therefore, we need only to focus on the pairs (C, S) in {({∧, ¬}, {+, -}), ({∨, ¬}, {+, -})}.

Let (C, S) be one of these two pairs, and let (G, Γ) be in GBC,S[c, c,∞]. Consider an algorithm that iterates over each goalbase Gi in {G1, . . . ,Gk} = G and over each subset G′i of Gi. At each iteration, we build the formula

Then, for each set {G′1 , . . . ,G′k } with G′i ⊆ Gi, we look for an interpretation σ{G′1 ,...,G′k } such that σ{G′1 ,...,G′k } |= Φ{G′1 ,...,G′k }, where Φ{G′1 ,...,G′k } = Γ ∧ ΦG′1 ∧ · · · ∧ ΦG′k .

In fact, the weighted formulas included in Gi and satisfied by σ{G′1 ,...,G′k } are precisely those in G′i (and the associated egalitarian value can be immediately computed given

σ{G′1 ,...,G′k }). Eventually, the feasible interpretation with the best possible egalitarian value will be returned. Now, observe that the computation requires a polynomial number of steps, since h1 and h2 are bounded by some constant. Moreover, we can decide in polynomial time whether Φ{G′1 ,...,G′k } is satisfiable and that, whenever this is the case, then a satisfying assignment can be actually computed in polynomial time, too. Indeed, just note that Φ{G′1 ,...,G′k } can be easily rewritten as a Boolean formula in conjunctive normal form, where only a constant number of clauses can contain more than one literal.

(Hardness Results) Consider first the case where C = {∧, ∨, ¬} and S = {+}. Given a Boolean formula ϕ, consider a variable X not in dom(ϕ). Consider the goalbases Gϕ = {〈X∧ϕ, 1〉, 〈¬X, 1〉} and ¯Gϕ = {〈X, 1〉}. It is immediate to check that ({Gϕ, ¯Gϕ},⊤) is normalized-w.l.o.g., ϕ is not valid, i.e., there is an assignment that makes ϕ false. Moreover, note that EG∗-VAL({Gϕ, ¯Gϕ}, ⊤) = 1 holds, if and only if, there is an interpretation σ where X evaluates true and such that Gϕ(σ) = 1. Hence, EG∗-VAL({Gϕ, ¯Gϕ},⊤) = 1 if, and only if, ϕ is satisfiable.

We conclude with the case C = {∧, ∨} and S = {+, -}. Consider again the formula ϕ and let be {X1, . . . ,Xn} the set of its variables. Let us build the formula ¯ ϕ where each occurrence of a literal ¬Xi is replacedwith the variable ¯Xi: ¯ ϕ is a formula over {X1, . . . ,Xn, ¯X1, . . . , ¯Xn} without negation, hence satisfiable. Let G = {〈Z∧(∨i (Xi∧ ¯Xi)), -1〉, 〈⊤, 1〉} and ¯G = {〈Z, 1〉}, where Z is a fresh variable. Note that the scenario ({G, ¯G}, ¯ ϕ) is normalized, and that EG∗-VAL({G, ¯G}, ¯ ϕ) = 1 if, and only if, ϕ is satisfiable. □

7 Conclusion

We have described and studied a general framework for group decision-making over combinatorial domains, where the representation of utility functions is made via weighted propositional formulas. We have characterized entirely the frontier of tractability with respect to meaningful restrictions on the number of agents, the number of formulas per agent, the number of different variables appearing in formulas, the syntax of formulas, and the signs of weights. Concerning the restrictions on the language, we point out that our fragments encode reasonable classes of preferences. For instance, positive formulas (without negation) are relevant for expressing preferences over sets of goods such as in fair division and auctions, while cubes (without disjunction) are relevant for representing the value of a coalition in coalitional games and also for some multiple referenda-expressive issues are analyzed in more details in [Uckelman et al., 2009].

Our approach contrasts with the study of specific frameworks, such as those in [Escoffier et al., 2013] and in other places. On the one hand, focusing on a specific problem (such as fair division) allows to obtain more precise, more specific results. On the other hand, the power of a general framework is that it allows to reason on new problems, before they are possibly investigated further. Avenues of further research include the study of other restrictions such as bounded weights, of the approximability of optimization for the intractable classes, and of determining the sets of agents who are most responsible for the loss of social welfare.

Acknowledgments

1. Greco's work was also supported by a Kurt G¨odel Research Fellowship, awarded by the Kurt G¨odel Society. J. Lang's work was also supported by the ANR-14-CE240007-01 project "CoCoRICo-CoDec".