# proportional_belief_merging__aef28cb8.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

Proportional Belief Merging

Adrian Haret, Martin Lackner, Andreas Pfandler, Johannes P. Wallner {haret, lackner, pfandler, wallner}@dbai.tuwien.ac.at TU Wien Vienna, Austria

In this paper we introduce proportionality to belief merging. Belief merging is a framework for aggregating information presented in the form of propositional formulas, and it generalizes many aggregation models in social choice. In our analysis, two incompatible notions of proportionality emerge: one similar to standard notions of proportionality in social choice, the other more in tune with the logic-based merging setting. Since established merging operators meet neither of these proportionality requirements, we design new proportional belief merging operators. We analyze the proposed operators against established rationality postulates, ﬁnding that current approaches to proportionality from the ﬁeld of social choice are, at their core, incompatible with standard rationality postulates in belief merging. We provide characterization results that explain the underlying conﬂict, and provide a complexity analysis of our novel operators.

1 Introduction Proportionality is one of the central fairness notions studied in social choice theory (Black 1958; Dummett 1984; Monroe 1995), arising whenever a collective decision should reﬂect the amount of support in favor of a set of issues. Thus, notions of proportionality are key when it is desirable that preferences of larger groups have more inﬂuence on the outcome, while preferences of smaller groups are not neglected. The idea of proportional representation shows up in many application scenarios: it is a key ingredient of parliamentary elections (Balinski and Young 1982) and, more generally, of multiwinner voting, i.e., the task of electing a committee of multiple candidates (Faliszewski et al. 2017). Recent work has set out to extend the notion of proportionality from mathematically simple formalisms (mainly the apportionment setting) to more general settings, with signiﬁcant progress in areas such as approval-based multiwinner voting (Aziz et al. 2017; S anchez-Fern andez et al. 2017), ordinal multiwinner voting (Elkind et al. 2017a; 2017b), proportional rankings (Skowron et al. 2017), and multi-attribute committees (Lang and Skowron 2018). In this paper we introduce proportionality to the very general framework of belief merging (Konieczny, Lang, and

Copyright 2020, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Marquis 2004; Konieczny and Pino P erez 2002; 2011), which allows agents to combine their individual positions on a set of issues in order to obtain a collective solution, with the added option of imposing constraints on admissible outcomes. Though the agents individual positions are called beliefs, the belief merging framework is versatile enough that it can accommodate a broad range of attitudes (e.g., beliefs, preferences, judgments, goals or items of knowledge), as long as these, together with the constraint and the outcome, can be expressed as formulas in a logical language. The key challenges of such a process are that agents may hold mutually conﬂicting beliefs, and that beliefs may reﬂect complex interdependencies between issues. The theory of belief merging then offers (i) a range of methods, called belief merging operators, for aggregating beliefs and (ii) postulates used to assess the rationality of the operators. The most prominent belief merging operators studied so far tend to fall into two main categories: operators following the majority opinion, and which can be said to embody a utilitarian stance; and operators that place particular emphasis on the worst-off agents, and which can be said to be based on an egalitarian viewpoint. Our aim is to ﬁnd a compromise between these two opposing positions, which, in a belief merging scenario, translates as the following desideratum: if a large enough proportion of the agents share common beliefs, then these beliefs should be reﬂected at the collective level, to a degree matching their proportion. Despite its intuitive appeal, such a proportionality requirement has yet to ﬁnd its way in the study of belief merging operators. In deﬁning proportional belief merging operators we rely on the Proportional Approval Voting (PAV) rule, studied in multiwinner voting scenarios and known to satisfy particularly strong proportionality requirements (Aziz et al. 2017). Based on PAV, we introduce three belief merging operators: the PAV operator, the bounded PAV operator and the harmonic Hamming operator. All these operators fall into the class of satisfaction-based operators, introduced by us (Section 4) as an alternative to the standard way of representing merging operators, which is distance-based. We look at the proposed belief merging operators from three perspectives. Firstly, in Section 5, the operators are placed against the standard belief merging IC-postulates. We

show that any belief merging operator directly extending PAV cannot be compatible with all IC-postulates; in particular, such an operator will not satisfy postulate IC2, which stipulates that any admissible agreement among agents shall be part of the merged result. We also provide a characterization of operators that fail IC2 based on properties of the ranking a satisfaction-based operator induces. This provides an alternative view of why the PAV approach is inconsistent with IC2. However, we show that what we call the bounded PAV operator can be characterized as the only merging operator (of a certain natural class) that extends PAV and satisﬁes all other postulates. While the harmonic Hamming operator is deﬁned via the harmonic sum used by PAV, it does not generalize PAV. Thus, the aforementioned impossibility does not hold; indeed, the harmonic Hamming operator satisﬁes all standard IC postulates IC0 8. Secondly, in Section 6, we introduce two basic proportionality postulates for the belief merging domain. The ﬁrst one, classical proportionality, is the kind of proportionality requirement typically studied in social choice settings, in particular in the apportionment setting (Balinski and Young 1982). This notion is based on the assumption that agents derive utility from positive occurrences, i.e., from approved candidates being selected in the collective choice. The second notion, binary proportionality, is closer to the logical nature of belief merging. Here, no difference is made between positive and negative agreement: the agents utility derives from the (Hamming) distance between their preferences and the collective choice. We show that these two notions are mutually exclusive and contradict each other. Furthermore, we show by example that established belief merging operators satisfy neither of these two postulates. In contrast, the aforementioned PAV and bounded PAV operators satisfy classical proportionality and the harmonic Hamming operator satisﬁes binary proportionality. Thirdly, in Section 7, we study the complexity of our proposed merging operators. Our results are that our novel operators fall into similar complexity classes as established merging operators, which shows that the introduction of proportionality comes at a moderate computational cost. As mentioned before, belief merging can be seen as a general framework. In Section 3 we make this argument precise for approval-based committee elections, and in Section 8 we show that our work has implications for other settings: in particular, it yields new proportional goal-based voting rules (Novaro et al. 2018) and approval-based multiwinner rules with a variable number of winners (Kilgour 2016; Faliszewski, Slinko, and Talmon 2017), and gives insights for proportional judgment aggregation (List and Puppe 2009; Everaere, Konieczny, and Marquis 2015; 2017).

2 Belief Merging We assume a set A of m propositional atoms, with L the set of propositional formulas generated from A using the usual connectives. An interpretation w is a truth-value assignment to atoms in A, and we denote by U the set of all interpretations over the set A. We typically write interpretations as words, standing in for the set of atoms assigned to true. If v and w are interpretations, the symmetric difference v w

between v and w is deﬁned as v w = (v\w) (w\v). The Hamming and drastic distances d H and d D, respectively, are deﬁned as d H(v, w) = |v w| and d D(v, w) = 0, if v = w, and 1 otherwise. If ϕ L is a propositional formula and w is an interpretation, w is a model of ϕ if w satisﬁes ϕ, with [ϕ] being the set of models of ϕ. If ϕ1, ϕ2 L, we say that ϕ1 |= ϕ2 if [ϕ1] [ϕ2], and that ϕ1 ϕ2 if [ϕ1] = [ϕ2]. A formula ϕ is consistent, or satisﬁable, if [ϕ] = . A propositional proﬁle P = (ϕ1, . . . , ϕn) is a ﬁnite tuple of consistent propositional formulas, with each formula ϕi assumed to correspond to an agent i. If P1 and P2 are proﬁles, P1 + P2 is the proﬁle obtained by appending P2 to P1. If there is no danger of ambiguity, we write P + ϕi instead of P + (ϕi). A merging operator Δ is a function mapping a proﬁle P of consistent formulas and a propositional formula μ, called the constraint, to a propositional formula Δμ(P). Operators Δ1 and Δ2 are equivalent if Δ1 μ(P) Δ2 μ(P), for any P and μ. The following postulates are typically taken to provide a core set of rationality constraints any merging operator Δ is expected to satisfy (Konieczny and Pino P erez 2002; 2011):

(IC0) Δμ(P) |= μ.

(IC1) If μ is consistent, then Δμ(P) is consistent.

(IC2) If P μ is consistent, then Δμ(P) P μ.

(IC3) If P1 P2 and μ1 μ2, then Δμ1(P1) Δμ2(P2).

(IC4) If ϕ1 |= μ and ϕ2 |= μ, then Δμ(ϕ1, ϕ2) ϕ1 is consistent if and only if Δμ(ϕ1, ϕ2) ϕ2 is consistent.

(IC5) Δμ(P1) Δμ(P2) |= Δμ(P1 + P2).

(IC6) If Δμ(P1) Δμ(P2) is consistent, then Δμ(P1 + P2) |= Δμ(P1) Δμ(P2).

(IC7) Δμ1(P) μ2 |= Δμ1 μ2(P).

(IC8) If Δμ1(P) μ2 is consistent, then Δμ1 μ2(P) |= Δμ1(P) μ2.

These postulates are best understood as axiomatizing a decision procedure based on the aggregation of information coming from different sources (the formulas in P), under a constraint μ that must be satisﬁed by the result (postulate IC0). The result should be consistent (postulate IC1), independent of the syntax of the formulas involved (postulate IC3), include outcomes that are unanimously accepted across subproﬁles (postulates IC5 6) and coherent when varying the constraint (postulates IC7 8). Additionally, postulate IC2 requires that if there is any agreement between the formulas in P and μ, then the merged result is nothing more than the agreed upon outcomes; and postulate IC4 stipulates that merging two formulas ϕ1 and ϕ2 should be fair, in the sense that if the result contains outcomes consistent with one of the formulas, it should contain results consistent with the other as well. We will see that the latter two postulates are problematic for proportionality-driven merging operators. Standard ways of constructing merging operators that satisfy postulates IC0 8 are based on the idea of minimizing overall distance to the proﬁle P = (ϕ1, . . . , ϕn), and rely on two ingredients (Konieczny and Pino P erez 2002;

2011). The ﬁrst ingredient is a notion of pseudo-distance d: U U R 0 between interpretations, typically either Hamming distance d H or drastic distance d D. The distance d(ϕ, w) from a formula ϕ to an interpretation w is then deﬁned as d(ϕ, w) = minv [ϕ] d(v, w). The collective distance w.r.t. proﬁle P is obtained using the second ingredient, an aggregation function f : Rn 0 R 0 that, for any integer n, maps a vector of n real numbers to a real number, and is deﬁned as df(P, w) = f(d(ϕ1, w), . . . , d(ϕn, w)). Typical aggregation functions are the sum Σ and gmax. By f = gmax vectors are ordered in descending order. For this aggregation function, the resulting ordered vectors are compared according to a lexicographic order. The distancebased merging operator Δd,f is deﬁned, for any proﬁle P and formula μ, as a formula Δd,f μ (P) such that [Δd,f μ (P)] = argminw [μ]df(P, w), i.e., as a formula whose models are the models of μ at minimal collective distance to P. When d = d D, the operators ΔD,Σ and ΔD,gmax are equivalent and we will refer to them as ΔD. Thus, we recall three main distance-based operators (ΔH,Σ, ΔH,gmax and ΔD), all of which are known to satisfy postulates IC0 8 (Konieczny, Lang, and Marquis 2002; Konieczny and Pino P erez 2011).

Example 1. For the set of atoms A = X Y , where X = {x1, . . . , x4} and Y = {y1, . . . , y4}, take a proﬁle P = (ϕ1, ϕ2, ϕ3, ϕ4) with ϕi = (x1 x2 x3 x4) ( y1 y2 y3 y4), for i {1, 2, 3}, ϕ4 = ( x1 x2 x3 x4) (y1 y2 y3 y4). We obtain that [ϕi] = {x1x2x3x4}, for i {1, 2, 3} and [ϕ4] = {y1y2y3y4}. Additionally, take a constraint μ such that [μ] = {x1x2x3x4, x1x2x3y1, x1x2y1y2, x1y1y2y3, y1y2y3y4}. Table 1 displays Hamming distances between models of μ and formulas in P as well as the aggregated distances, for the Σ and gmax aggregation functions. We have dΣ H(P, x1x2x3x4) < dΣ H(P, x1x2x3y1) and dgmax H (P, x1x2y1y2) < dgmax H (P, x1x2x3y1), since the overall distance (4, 4, 4, 4) lexicographically dominates (6, 2, 2, 2). Optimal outcomes are written in bold, i.e., [ΔH,Σ μ (P)] = {x1x2x3x4} and [ΔH,gmax μ (P)] = {x1x2y1y2}. We also obtain that [ΔD μ (P)] = {x1x2x3x4}.

Example 1 illustrates a general feature of the standard merging operators: ΔH,Σ sees optimal outcomes in utilitarian terms and thereby favors the majority opinion, while ΔH,gmax attempts to improve the standing of the worse off agent, thereby favoring an egalitarian outcome. While such approaches may produce, on occasion, proportional outcomes, they are in no way guaranteed to do so in general.

3 Approval-Based Committee Elections as Instances of Belief Merging

Notions of proportionality have been systematically studied in the social choice literature, notably in the case of Approval-Based Committee (ABC) elections (Faliszewski et al. 2017). An ABC election consists of a set of candidates C, a desired size of the committee k, and a preference proﬁle A = (A1, . . . , An). The preference proﬁle A contains approval ballots, i.e., Ai C is the set of candidates agent i approves of. An ABC voting rule outputs one or more sizek subsets of C, the chosen committee(s). The ABC voting

rule of interest to us is called Proportional Approval Voting (PAV) (Thiele 1895). It is based on the harmonic function h: N R, deﬁned as h(ℓ) = ℓ i=1 1

i with the added convention that h(0) = 0. Given a committee w of size k, the PAV-score of w w.r.t. A is PAV(A, w) = n i=1 h(|Ai w|). The PAV rule applied to the preference proﬁle A, for a desired size k of the committee, is deﬁned as PAVk(A) = argmaxw C,|w|=k PAV(A, w), i.e., it outputs committees of size k that maximize the PAV score w.r.t. A.

Example 2. Take a set C = X Y of candidates, where X and Y are as in Example 1, and a preference proﬁle A = (A1, A2, A3, A4) with Ai = [ϕi], where ϕi are as in Example 1. Suppose k = 4, i.e., the task is to choose committees of size 4. Intuitively, a proportional outcome would consist of three candidates from X and one from Y , to reﬂect the fact that supporters of X outnumber supporters of Y in A by a ratio of 3 : 1. Indeed, this is exactly the type of outcome PAV will select. A committee maximizing the overall PAV score w.r.t. A is x1x2x3y1, as depicted in Table 2.

In Example 2 we have identiﬁed models of propositional formulas with sets of approved candidates in an ABC election. Indeed, we may pursue this analogy further and show that any ABC election can be rephrased as a belief merging instance. Given an instance of an ABC election, we associate to C the set of propositional atoms AC = C. To agent i s approval ballot Ai C we associate the propositional formula: ϕAi =

x C\Ai x, the sole model of which is Ai. To the preference proﬁle A we associate the propositional proﬁle PA = (ϕA1, . . . , ϕAn). To obtain solutions that adhere to the cardinality constraint k, we choose μk to be a formula whose models are all subsets of AC of size k. By postulates IC0 and IC1, [Δμk(PA)] consists of a non-empty set of models of size k, which can be seen as the winning committees of the ABC election. In general, any ABC election for size-k committees can be seen as a belief merging instance where the proﬁle consists of formulas with exactly one model and the constraint μ has models of ﬁxed size k. A merging operator Δ extends PAV if for all preference proﬁles A, it holds that PAVk(A) = [Δμk(PA)], i.e., the output of the PAV voting rule is the set of interpretations, or sets of atoms, returned by Δμk(PA). In the following we will introduce merging operators that extend PAV and another one that is inspired by it.

4 Satisfaction-based Merging Operators

The framework of ABC elections presented in Section 3 can be used as a springboard for designing proportional belief merging operators. By conceiving ways in which an agent derives utility from a possible outcome, it becomes possible to reason about the social welfare of merging, i.e., the utility of the agents society as a whole. The key notion in doing so is a satisfaction measure s: U U R, quantifying the amount of satisfaction s(v, w) of interpretation v with interpretation w. The satisfaction s(ϕ, w) of a formula ϕ with w is then deﬁned as s(ϕ, w) = maxv [ϕ] s(v, w). Finally, the collective satisfaction s(P, w) of a proﬁle P with w is deﬁned as

d H x1x2x3x4 x1x2x3x4 x1x2x3x4 y1y2y3y4 Σ gmax

x1x2x3x4 0 0 0 8 8 (8, 0, 0, 0) x1x2x3y1 2 2 2 6 12 (6, 2, 2, 2) x1x2y1y2 4 4 4 4 16 (4, 4, 4, 4) x1y1y2y3 6 6 6 2 20 (6, 6, 6, 2) y1y2y3y4 8 8 8 0 24 (8, 8, 8, 0)

Table 1: Hamming distances for ΔH,Σ and ΔH,gmax.

PAV x1x2x3x4 x1x2x3x4 x1x2x3x4 y1y2y3y4 Σ

x1x2x3x4 h(4) h(4) h(4) h(0) 6.25 x1x2x3y1 h(3) h(3) h(3) h(1) 6.5 x1x2y1y2 h(2) h(2) h(2) h(2) 6 x1y1y2y3 h(1) h(1) h(1) h(3) 4.83 y1y2y3y4 h(0) h(0) h(0) h(4) 2.08

Table 2: PAV scores for a selection of committees of size 4.

Figure 1: Proposed satisfaction measures.

ϕ P s(ϕ, w). The satisfaction-based merging operator Δs outputs a formula Δs μ(P) such that [Δs μ(P)] = argmaxw [μ]s(P, w), i.e., a formula whose models are exactly the models of μ that maximize satisfaction of P. Note that we can convert a distance-based merging operator Δd,Σ (see Section 2) into an equivalent satisfactionbased operator by inverting the pseudo distance d, i.e., by deﬁning a satisfaction measure s as s(v, w) = m d(v, w), for any interpretations v and w (remember that m is the number of atoms in A). The resulting satisfaction-based operator is s.t. Δs μ(P) Δd,Σ μ (P), for any proﬁle P and μ. Note that since d is a pseudo distance and thus symmetric (i.e., d(v, w) = d(w, v), for any interpretations v and w), the satisfaction measure s deﬁned on the basis of it is also symmetric. This being said, we do not require satisfaction measures to be symmetric in general. Consequently, satisfactionbased operators as deﬁned here form a more general class than distance-based operators Δd,Σ, where d is a pseudodistance. It is worth mentioning that the satisfaction-based approach we propose here is not a mere stylistic variant of the distance-based view; it also encourages a different viewpoint on merging, where the goal is to ﬁnd an outcome making agents happy, subject to fairness norms. Scenarios where this viewpoint is warranted occur most of all in settings requiring social considerations. The concrete satisfaction measures we propose are deﬁned, for any interpretations v and w, in Figure 1, and generate two groups of operators. The approval-based operators, consisting of the AV operator ΔAV, the PAV operator ΔPAV and the bounded PAV operator Δb PAV, mimic the

behavior of an ABC voting rule (see Section 3) in that they compute satisfaction of v with w based on how many atoms v and w have in common, similarly to how satisfaction of an approval ballot Ai with a potential committee w is based on how many approved candidates in Ai ﬁnd themselves in w. Note that, while an ABC voting rule is deﬁned only for committees of ﬁxed size, the merging operators we propose select among interpretations of any size. Nonetheless, it is straightforward to see that if the allowed outcomes (here, models of the constraint μ) are restricted to a given size, then the operators ΔPAV and Δb PAV are equivalent and extend, in the sense described in Section 3, the PAV voting rule. The operator ΔAV is put forward as a benchmark approval-based operator, based on a satisfaction measure that simply counts the atoms v and w have in common: in particular, ΔAV does not incorporate any proportionality ideas. Consequently the ΔAV operator does not extend PAV, and, as shown in Section 6, does not meet any of the proportionality requirements we propose. The ΔPAV operator reﬁnes ΔAV by using the harmonic function h, which is known to behave well w.r.t. proportionality requirements (Aziz et al. 2017). Intuitively, the harmonic function reﬂects the diminishing returns of added satisfaction: the difference between h(x) and h(x + 1) gets smaller as x increases. Thus, the operator ΔPAV is a prime candidate for a proportional satisfaction-based merging operator. Nonetheless, ΔPAV has several shortcomings, which serve as motivation for the remaining operators. One drawback of ΔPAV is that it favors larger interpretations if available (Example 3), i.e., it tries to increase agents satisfaction by setting as many atoms to true as possible. Such an inﬂationary strategy may be undesirable in practice and, in a belief merging setting, interferes with postulate IC4. Example 3. For A = {x1, x2}, P = (ϕ1, ϕ2), with [ϕ1] = {x1} and [ϕ2] = {x1x2}, and μ such that [μ] = {x1, x1x2}, we obtain that [ΔPAV μ (P)] = {x1x2}, contradicting IC4. The same result is obtained for ΔAV, but [Δb PAV μ (P)] = {x1, x1x2}, which is in accordance with IC4. To curb the inﬂationary tendencies of ΔPAV, operator Δb PAV introduces a penalty on interpretations depending on their size, in the process ensuring satisfaction of postulate IC4 as well. Indeed, as Section 5 shows, Δb PAV is the only operator from a fairly broad class that manages to balance proportionality and fairness, as formalized by postulate IC4. Note, however, that sb PAV is not symmetric. Example 4. It holds that sb PAV(x, xy) < sb PAV(xy, x). Intuitively, this means it is worse to get y if it is not wanted

than to not get it if it is wanted. A related problem with ΔPAV stems from the fact that s PAV(v, w) is obtained by counting only atoms v and w have in common. Hence, ΔPAV has a bias towards positive literals, which turns out to interfere with postulate IC2. The binary satisfaction-based operators, consisting of the harmonic drastic operator Δh D and the harmonic Hamming operator Δh H, are introduced in an attempt to deal with the effect of unwanted atoms while, at the same time, providing proportional outcomes. The satisfaction measures they are based on penalize interpretations w if they include atoms for which an explicit preference is not stated. This is done by inverting familiar notions of distance, which pay attention to atoms appearing in one of the interpretation but not in the other, and leads to an equal treatment of positive and negative literals. The harmonic function h is applied to this satisfaction notion, with the idea of ensuring proportionality. The operators that emerge are worth investigating: neither of them extends PAV (as hinted at in Example 5), but from this point onward their properties diverge. Though Δh H does not extend PAV, it still ends up having interesting proportionality properties, formalized in Section 6. Example 5. It holds that s PAV(x1, x1) = s PAV(x1, x1x2). The assumption behind s PAV is that an agent who wants x1 is equally satisﬁed with x1x2 as it is with x1, i.e., is not bothered by the presence of x2. This leads to non-satisfaction of IC2: for A = {x1, x2}, P = (ϕ), [ϕ] = {x1} we obtain that [ΔPAV (P)] = {x1, x1x2}, contrary to IC2. On the other hand, sh H(x1, x1) = h(2), while sh H(x1, x1x2) = h(1) and [Δh H μ (P)] = {x1}, in accordance with IC2. Thus, according to sh H, x1x2 provides less satisfaction to x1 than x1 alone, i.e., the agent is bothered by the presence of x2, for which an explicit preference was not stated. The operator Δh D turns out to be so coarse in its assessment of satisfaction as to become, as Proposition 1 shows, indistinguishable from existing merging operators deﬁned using drastic distance d D. As a result, the Δh D operator is not responsive to proportionality requirements. Proposition 1. The satisfaction-based operator Δh D is equivalent to the distance-based operator ΔD. What emerges is a landscape with three merging operators relevant to the issue of proportionality, i.e., ΔPAV, Δb PAV and Δh H. Out of these, Δb PAV and Δh H address, each in its own way, problems arising with the ΔPAV operator: Δb PAV penalizes interpretations according to their size, while Δh H uses an approach reminiscent from logic, where positive and negative literals are treated equally. As we will see in Sections 5 and 6, the proposed solutions involve various tradeoffs between proportionality and the IC postulates.

5 IC Postulates: Possibility and Impossibility In this section we analyze the merging operators introduced in Section 4 in light of the standard merging postulates IC0 8. The ﬁrst result shows that any satisfaction-based operator satisﬁes a core set of IC-postulates. Proposition 2. If s is a satisfaction measure, then the merging operator Δs satisﬁes postulates IC0 1,3,5 8.

Proposition 2 applies to both the approval-based and the harmonic distance-based operators. What remains, then, is an understanding of how the new satisfaction measures interact with postulates IC2 and IC4, and we settle the issue by characterizing the types of satisfaction measures compliant with these postulates. If v = w, the following properties prove to be relevant: (S1) s(v, v) > s(v, w); (S2) s(v, v) > s(w, v); (S3) s(v, v) = s(w, w); (S4) s(v, w) = s(w, v).

They formalize the intuition that satisfaction is symmetric (S4), maximal when one gets exactly what one wants, and trailing off as the outcome diverges from one s most desired outcome (S1 3). Theorem 1 shows that properties S1 3 capture satisfaction measures compliant with postulate IC2. Theorem 1. A satisfaction-based merging operator Δs satisﬁes postulate IC2 iff s satisﬁes properties S1 3. Since the satisfaction measures s AV, s PAV or sb PAV satisfy none of the properties S1 3, Theorem 1 implies that the approval-based operators ΔAV, ΔPAV or Δb PAV do not satisfy postulate IC2. On the other hand, the satisfaction measures sh D and sh H do satisfy properties S1 3, showing that the corresponding operators satisfy postulate IC2. As mentioned in Section 4, we do not require satisfaction measures to be symmetric and, indeed, sb PAV is not symmetric (though the other satisfaction measures are). The following result shows that, in the presence of postulate IC2, symmetry is connected to postulate IC4. Theorem 2. If a satisfaction-based merging operator Δs satisﬁes postulate IC2, then Δs satisﬁes postulate IC4 if and only if s also satisﬁes property S4 (i.e., is symmetric). Since the satisfaction measures sh D and sh H are symmetric and, as implied by Theorem 1, satisfy properties S1 3, we get by Theorem 2 that they also satisfy postulate IC4. Together with Proposition 2, this yields the full picture for the binary satisfaction-based operators Δh H and Δh D. Corollary 1. The operators Δh H and Δh D satisfy postulates IC0 8. For the approval-based operators, satisfaction of postulates IC2 and IC4 is clariﬁed by another perspective on satisfaction measures. A satisfaction measure s is a counting index if there exists a function σ: N N R, called the witness of s, such that σ(0, 0) = 0 and s(v, w) = σ(|v w|, |w|), for any interpretations v and w. Theorem 3 shows that counting indices do not ﬁt with postulate IC2. Theorem 3. If s is a counting index, the satisfaction-based merging operator Δs does not satisfy postulate IC2. It is straightforward to see that the approval-based satisfaction measures introduced in Section 4 are counting indices. Thus, by Theorem 3, none of the operators they generate satisﬁes postulate IC2. For postulate IC4, however, the situation is different. Example 3 shows that the ΔAV and ΔPAV operators do not satisfy postulate IC4, though Δb PAV manages to evade the counter-example. In fact, it turns out that not only does the operator Δb PAV satisfy postulate IC4, but a much stronger result can be shown: it is the only operator based on a counting index that does so.

Theorem 4. If Δs is a satisfaction-based merging operator such that s is a counting index with σ as witness, extends PAV and satisﬁes postulate IC4, then σ(x, y) = 2h(x) h(y), for any x, y R. It deserves emphasis that Δb PAV manages to satisfy postulate IC4 even though sb PAV is not a symmetric satisfaction measure: since Δb PAV does not satisfy IC2, Theorem 2 does not apply. Indeed, none of the approval-based operators manages to satisfy both IC2 and IC4. This suggests that there is a trade-off between the kind of proportionality these operators stand for and the satisfaction of IC2 and IC4. It is relevant that approval-based operators can consider interpretations of various sizes: reﬂection on Examples 3 and 5 shows that they are at the root of the problematic situations. Interestingly, it turns out that ﬁxing the size of the models of the constraint μ yields merging operators that behave well w.r.t. the IC postulates. Theorem 5. If all models of the constraint μ have some ﬁxed size k, then the approval-based merging operators ΔAV, ΔPAV and Δb PAV satisfy all postulates IC0 8.

6 Two Types of Proportionality Here we formalize two notions of proportionality, arising out of two different ways of conceptualizing satisfaction with respect to a possible outcome. For the sake of clarity, we deﬁne these notions for rather restricted proﬁles. A formula ϕ is complete if it has exactly one model, and a proﬁle P is complete if all its formulas are complete. We write P = (v1, . . . , vn) to denote the complete proﬁle with [ϕi] = {vi}, for all i {1, . . . , n}. A complete proﬁle P = (v1, . . . , vn) is simple if v1 vn = A, and either vi = vj or vi vj = , for every i, j {1, . . . , n}.1 A complete proﬁle P = (v1, . . . , vn) is ℓ-simple if it is simple and |{v1, . . . , vn}| = ℓ, i.e., P contains ℓdistinct sets. If v1, . . . , vℓconstitutes a partition of A, and p1, . . . , pℓ are positive integers, we write (vp1 1 , . . . , vpℓ ℓ) to denote the ℓ-simple proﬁle: (v1, . . . , v1 p1 times

, v2, . . . , v2 p2 times

, . . . , vℓ, . . . , vℓ pℓtimes

P = (vp1 1 , . . . , vpℓ ℓ) is an ℓ-simple proﬁle with ℓ i=1 pi = n, we say that P is k-integral if k pi

n is an integer, for every i {1, . . . , ℓ}. Intuitively, for a model w of μ of size k, the fraction k pi

n denotes the intended satisfaction if proportionality is taken into account: out of the k atoms selected, the share of group i should be the relative size of the group. We propose two proportionality postulates, formulated for simple proﬁles P = (vp1 1 , . . . , vpℓ ℓ). As in Section 3, constraint μk has as its models all interpretations of size k. (ICcp) For any k {1, . . . , m} and w [Δμk(P)], it holds that if P is k-integral and |vj| k pj

n for each j, 1 j l, then |vi w| = k pi

n , for all i {1, . . . , ℓ}.

(ICbp) If P = (vp1 1 , vp2 2 ) is simple and there is a w [μ] such that m d H(vi, w) = m pi

n for i {1, 2}, then this equality holds for all w [Δμ(P)].

1In the context of ABC voting, such proﬁles are referred to as party-list proﬁles (Lackner and Skowron 2018b).

We refer to ICcp and ICbp as postulates of weak classical proportionality and weak binary proportionality, respectively, as they refer to different sources of satisfaction. Postulate ICcp talks about classical satisfaction, in which agent i s satisfaction with an interpretation w is given by |vi w|, just like the satisfaction with a committee in an ABC election is measured by the number of approved committee members. This is the kind of satisfaction notion typically used in a social choice context. Postulate ICbp talks about binary satisfaction, in which agent i s satisfaction with w is given by m d H(vi, w), i.e., by the closeness between vi and w. This type of satisfaction, alluded to already in Section 4, follows from a logical viewpoint where positive and negative variable assignments are treated equally. This approach is better suited to deal with interpretations of varying sizes than the classical one, and thus postulate ICbp allows such interpretations to be selected. Intuitively, both postulates stipulate shares groups of agents shall receive (under a classical or binary viewpoint) that meet proportionality based on the relative size of the groups. For ICcp we restrict to μk, with k atoms to be distributed proportionally by each solution w (like for ABC elections). Postulate ICbp states that in the presence of at least one admissible w [μ] that meets the proportionality requirements, all solutions shall meet said requirements (otherwise μ permits no proportional solution). Note that if P = (vp1 1 , vp2 2 ) satisﬁes the conditions of ICbp, then P is mintegral, and the binary satisfaction of v1 and v2 adds up to m, i.e., m d H(v1, w)+m d H(v2, w) = m. Postulate ICbp demands that this total satisfaction m is split proportionally. Example 6. For A = X Y , with X = {x1, . . . , x6} and Y = {y1, y2}, take the simple proﬁle P = (v3 1, v1 2), with v1 = x1 . . . x6 and v2 = y1y2, and a constraint μ4, with models of size 4. According to ICcp, an optimal outcome contains three variables from X and one from Y , e.g., the interpretation w = x1x2x3y1. Such an outcome is in the spirit of classical proportionality. According to postulate ICbp, an optimal outcome w would be such that d H(v1, w) = 2 and d H(v2, w) = 6, e.g., w = x1x2x3x4, w = x1x2x3x4x5y1 or w = x1x2x3x4x5x6y1y2. Note, ICbp allows interpretations of varying sizes to be selected. If the size is restricted to 4 (i.e., the constraint is μ4), then the outcome narrows down to interpretations such as w , consisting of four atoms from X. Example 6 shows that classical and binary proportionality may require different interpretations to be selected on the same input. Thus, even though our notions of proportionality apply only to simple proﬁles, they set up a clear boundary for distinguishing among the different merging operators. Theorem 6. The merging operators ΔPAV and Δb PAV satisfy postulate ICcp, Δh H satisﬁes postulate ICbp, while ΔH,Σ, ΔH,gmax, Δh D and ΔAV satisfy neither ICcp nor ICbp. The proposed merging operators ΔPAV and Δb PAV are representative of the notion of classical proportionality, while Δh H is representative for binary proportionality. Theorem 7 shows that these notions are thoroughly incompatible. Theorem 7. There is no merging operator that satisﬁes IC1 and both ICcp and ICbp.

Table 3: Summary of results. New results in gray, for all others see (Konieczny, Lang, and Marquis 2004)). Per Theorem 5, for results marked with the becomes when models of the constraint μ are assumed to have ﬁxed size.

IC0,1,3,5 8 IC2 IC4 ICcp ICbp Complexity

ΔH,Σ ΘP 2 -c ΔH,gmax ΔP 2 -c Δh D ΔD ΘP 2 -c Δh H in ΔP 2 , ΘP 2 -h ΔAV ΘP 2 -c ΔPAV in ΔP 2 , ΘP 2 -h Δb PAV in ΔP 2 , ΘP 2 -h

The literature on belief merging suggests other properties concerned, in some way or another, with fairness of merging operators (Konieczny and Pino P erez 2002; Everaere, Konieczny, and Marquis 2010; 2014). In the interest of brevity, we mention only that these properties are largely orthogonal to the proportionality requirements we study here. The one exception is the majority axiom (Konieczny and Pino P erez 2002), which our operators do satisfy.

7 Computational Complexity

To investigate the complexity of our novel merging operators, we look at the standard decision problem studied in this context (Konieczny, Lang, and Marquis 2004): given an operator Δ, a proﬁle P, an integrity constraint μ, and a Boolean formula ψ, determine whether Δμ(P) |= ψ holds. That is, the decision problem asks whether formula ψ follows from the merged result. The hardness results we use and recall here hold when ψ = a is an atom. The two main complexity classes appearing here are ΔP 2 and ΘP 2 , denoting the classes of decision problems solvable via a deterministic polynomial time algorithm with access to an NP oracle, with the latter class having the additional restriction that at most logarithmically many oracle calls may be made. Many standard merging operators are complete for one of these two classes (Konieczny, Lang, and Marquis 2004). We show that our novel operators ﬁt into this picture; we obtain ΘP 2 hardness and ΔP 2 membership for all new operators, except for ΔAV, which we show to be ΘP 2 -complete. That is, our introduction of proportionality leads to neither milder nor signiﬁcantly more complex operators. Hardness for ΘP 2 can be shown by adapting an existing reduction, originally from belief revision (Eiter and Gottlob 1992, Theorem 6.9). Finally, membership diverges for Δh H, ΔPAV, Δb PAV and ΔAV, since the ﬁrst three operators induce an exponential set of possible satisfaction scores for interpretations in contrast to ΔAV that only induces a polynomial set.

Theorem 8. Deciding whether a formula follows from the result of merging operator Δs is ΘP 2 -complete for s = AV, and both ΘP 2 -hard and in ΔP 2 , for s {PAV, b PAV, h H}.

We conjecture that merging under Δh H, ΔPAV and Δb PAV is ΔP 2 -complete.

8 Applications Beyond Belief Merging

In this section we brieﬂy discuss how our results can be transferred to other, related formalisms.

Variable Approval-Based Committee Elections In contrast to ABC elections as introduced in Section 3, it is sometimes desirable to have ﬂexibility with respect to the size of the committee by not ﬁxing its size in advance (Kilgour 2016; Faliszewski, Slinko, and Talmon 2017). We refer to ABC voting rules without a size constraint as variable ABC voting rules. Note that a merging operator deﬁnes a variable ABC rule by setting μ = . It is easy to see that the AV and PAV operators are not sensible in this context, as w = A (i.e., setting all atoms to true) is always an optimal model. However, the Δb PAV and Δh H operators present themselves as novel additions to this framework, being proportional variable ABC rules.

Goal-Based Voting Goal-based voting (Novaro et al. 2018) is a formalism similar to belief merging but with a focus on resolute rules (i.e., rules return only one model) and with different postulates. All proposed operators in this paper can be viewed as goal-based voting rules (subject to tiebreaking), and our proportionality postulates can be adapted for this setting as well. To the best of our knowledge, our proposed merging operators yield the ﬁrst proportional goalbased voting rules. It would be particularly interesting to see whether Theorem 4 can be replicated by axioms from the goal-based voting setting (instead of postulate IC4).

Judgment Aggregation Judgment aggregation (JA) is another formalism for aggregating beliefs, distinct from belief merging but overlapping in certain respects (Everaere, Konieczny, and Marquis 2015; 2017). Even though they differ in important aspects, the main ideas in our paper can be transferred to JA. While propositional variables are the basic building blocks for belief merging, it might be more suitable to take the agenda (a set of propositional formulas) as the basis for deﬁning proportionality in JA. This allows for the deﬁnition of proportional JA operators. Further work is required to analyze the resulting JA operators.

9 Discussion

In this paper we have initiated the study of proportional belief merging operators. We have presented three proportional

operators: the PAV operator and the bounded PAV operator, both satisfying ICcp, and the harmonic Hamming operator satisfying ICbp. We summarize our results in Table 3. Apart from the questions posed in Section 8, the current work suggests several directions for future research. While the two proportionality postulates we proposed apply only to certain instances, even weak proportionality postulates have proven sufﬁcient for axiomatic characterizations (Lackner and Skowron 2018b) and in our paper these two postulates are sufﬁcient to distinguish proportional from non-proportional operators. On the other hand, stronger postulates are desirable to determine to which degree proportionality guarantees can be given. This has recently been investigated in the context of approval-based committee elections (Aziz et al. 2017; 2018; S anchez-Fern andez et al. 2017); this line of work can serve as a basis for a similar analysis for belief merging operators. Finally, manipulation and strategic voting, common concerns in social choice theory, have received some attention in the belief merging framework as well (Everaere, Konieczny, and Marquis 2007; Haret and Wallner 2019). It can be expected that proportional belief merging operators are prone to strategic voting, as in ABC voting even weak forms of proportionality and strategy-proofness have been shown to be incompatible (Peters 2018). Still, it has been found that the percentage of manipulable instances depends strongly on the choice of voting rules (Lackner and Skowron 2018a), indicating that a detailed analysis of vulnerabilities is an interesting avenue for future work.

Acknowledgements This work was supported by the Austrian Science Fund (FWF): P30168-N31, P30930-N35, P31890-N31, and W1255-N23.

References Aziz, H.; Brill, M.; Conitzer, V.; Elkind, E.; Freeman, R.; and Walsh, T. 2017. Justiﬁed representation in approval-based committee voting. Soc. Choice Welf. 48(2):461 485. Aziz, H.; Elkind, E.; Huang, S.; Lackner, M.; Fern andez, L. S.; and Skowron, P. 2018. On the complexity of extended and proportional justiﬁed representation. In Proc. AAAI, 902 909. AAAI Press. Balinski, M., and Young, H. P. 1982. Fair Representation: Meeting the Ideal of One Man, One Vote. Yale University Press. Black, D. 1958. The Theory of Committees and Elections. Cambridge University Press. Dummett, M. 1984. Voting Procedures. Oxford University Press. Eiter, T., and Gottlob, G. 1992. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artif. Intell. 57(2-3):227 270. Elkind, E.; Faliszewski, P.; Laslier, J.-F.; Skowron, P.; Slinko, A.; and Talmon, N. 2017a. What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain. In Proc. AAAI, 494 501. AAAI Press. Elkind, E.; Faliszewski, P.; Skowron, P.; and Slinko, A. 2017b. Properties of multiwinner voting rules. Soc. Choice Welf. 48(3):599 632. Everaere, P.; Konieczny, S.; and Marquis, P. 2007. The strategyproofness landscape of merging. J. Artif. Intell. Res 28:49 105.

Everaere, P.; Konieczny, S.; and Marquis, P. 2010. Disjunctive merging: Quota and gmin merging operators. Artif. Intell. 174(1213):824 849. Everaere, P.; Konieczny, S.; and Marquis, P. 2014. On egalitarian belief merging. In Proc. KR, 121 130. AAAI Press. Everaere, P.; Konieczny, S.; and Marquis, P. 2015. Belief merging versus judgment aggregation. In Proc. AAMAS, 999 1007. ACM. Everaere, P.; Konieczny, S.; and Marquis, P. 2017. An introduction to belief merging and its links with judgment aggregation. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 7, 123 143. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner voting: A new challenge for social choice theory. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 2, 27 47. Faliszewski, P.; Slinko, A.; and Talmon, N. 2017. The complexity of multiwinner voting rules with variable number of winners. Co RR abs/1711.06641. Haret, A., and Wallner, J. P. 2019. Manipulating skeptical and credulous consequences when merging beliefs. In Proc. JELIA, volume 11468 of LNCS, 133 150. Springer. Kilgour, M. D. 2016. Approval elections with a variable number of winners. Theory Decis. 81(2):199 211. Konieczny, S., and Pino P erez, R. 2002. Merging information under constraints: A logical framework. J. Log. Comput. 12(5):773 808. Konieczny, S., and Pino P erez, R. 2011. Logic based merging. J. Philosophical Logic 40(2):239 270. Konieczny, S.; Lang, J.; and Marquis, P. 2002. Distance based merging: A general framework and some complexity results. In Proc. KR 2002, 97 108. Morgan Kaufmann.

Konieczny, S.; Lang, J.; and Marquis, P. 2004. DA2 merging operators. Artif. Intell. 157(1-2):49 79. Lackner, M., and Skowron, P. 2018a. Approval-based multi-winner rules and strategic voting. In Proc. IJCAI, 340 346. ijcai.org. Lackner, M., and Skowron, P. 2018b. Consistent approval-based multi-winner rules. In Proc. EC, 47 48. ACM. For details, see ar Xiv long version ar Xiv:1704.02453. Lang, J., and Skowron, P. 2018. Multi-attribute proportional representation. Artif. Intell. 263:74 106. List, C., and Puppe, C. 2009. Judgment aggregation: A survey. In Anand, P.; Pattanaik, P.; and Puppe, C., eds., The Handbook of Rational and Social Choice. Oxford University Press. chapter 19. Monroe, B. 1995. Fully proportional representation. Am. Polit. Sci. Rev. 89(4):925 940. Novaro, A.; Grandi, U.; Longin, D.; and Lorini, E. 2018. Goalbased collective decisions: Axiomatics and computational complexity. In Proc. IJCAI, 468 474. ijcai.org. Peters, D. 2018. Proportionality and strategyproofness in multiwinner elections. In Proc. AAMAS, 1549 1557. IFAAMAS / ACM. S anchez-Fern andez, L.; Elkind, E.; Lackner, M.; Fern andez, N.; Fisteus, J. A.; Val, P. B.; and Skowron, P. 2017. Proportional justiﬁed representation. In Proc AAAI, 670 676. AAAI Press. Skowron, P.; Lackner, M.; Brill, M.; Peters, D.; and Elkind, E. 2017. Proportional rankings. In Proc IJCAI, 409 415. ijcai.org. Thiele, T. N. 1895. Om ﬂerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger. 415 441.