On the links between belief merging,the Borda voting method,and the cancellation property 1

Abstract

In this work, we explore the links between the Borda voting rule and belief merging operators. More precisely, we define two families of merging operators inspired by the definition of the Borda voting rule. We also introduce a notion of cancellation in belief merging, inspired by the axiomatization of the Borda voting rule proposed by Young. This allows us to provide a characterization of the drastic merging operator and of a family of merging operators defined in a way which is similar to the Borda rule.

Keywords

Belief merging Borda rule cancellation

1. Introduction

Belief merging operators aim at synthesizing a set of conflicting belief bases in order to form a coherent view of the world. To this aim, these operators benefit from the complementarity of the belief bases, which allows to generate new pieces of information that are distributed in the belief bases, while solving the logical conflicts between these bases.

Belief merging [19,20,22,24,25,32] can be considered as the intersection of two research topics. The first one is belief revision [2,14–16], where the problem is to correct the beliefs of the agent by a (more reliable) piece of information. In both revision and merging the problem is to find the most plausible information given the input. The difference is that for revision the input is a single belief base, whereas for merging it is a set of such bases. So the principles governing these two problems are closely related. The second research topic is group decision as studied in social choice theory [3,4], and especially in voting methods. The aim of a voting method is to define a social preference (a preference for the whole group) from a set of individual preferences given by the individuals. Similarly belief merging aims at defining the “beliefs of the group” from the beliefs provided by several sources. So social choice (particularly voting methods) and belief merging share concern about how to faithfully take into account the set of inputs (preferences for vote, beliefs for merging).

Formal links between belief merging and belief revision are well known. For instance it is easy to show that belief revision can be considered as a special case of belief merging when there is a single belief base in the profile [20].

Links between belief merging and social choice theory have also been investigated. For instance in [21] there is a comparison between social choice functions and belief merging operators. Some questions coming from social choice and voting methods have also been investigated in the context of belief merging. For instance, [8] studies the manipulation issue for merging operators. [9] investigates the problem of finding the truth (truth-tracking) and a generalization of Condorcet’s Jury Theorem for belief merging operators is given. Some egalitarian belief merging operators were proposed using standard techniques coming from social choice [11]. A generalisation of Arrow’s impossibility Theorem in the framework of belief merging is given in [28]. Finally, some works on judgment aggregation and its link with belief merging have been done [13,31]. Judgment aggregation can be seen as an intermediate issue between voting and belief merging. As in belief merging, judgment aggregation [12,23,26,27,30] works from logical formulae, and as in (multiple) vote (and contrarily to merging), there is an agenda (a set of formulae) on which the group has to decide.

We have to mention that the Borda rule has been adapted to the judgment aggregation and binary aggregation framework, which is related to belief merging. However the “alternatives” in the present paper are all the interpretations while in judgment aggregation the agenda is fixed, see [6,7]

In this work we want to investigate a more direct and more technical link between some merging operators and a voting method. In fact a wide class of belief merging operators is the class of distance-based merging operators [18,22]. These operators use a distance in order to generate an evaluation of the plausibility of each possible world with respect to each belief base from the input profile, and then they use an aggregation function in order to obtain a global evaluation of the plausibility of each possible world.

Actually, Borda-like aggregators are considered in the seminal work on Belief Merging [20]. They are the operators of the form $Δ^{d, Σ}$ (operators built with a distance and the sum aggregator). In the present work we relax the constraint that all the agents use the same process (a distance) to form their plausibility orders over the worlds. We propose a general way to do that. This is done via the generating functions.

Several aggregation functions can be considered in order to give rise to sensible operators, like the sum [25,32], the leximax [20], the sum of the n^th powers [21], the leximin [10], etc.

When using the sum as aggregation function, the corresponding operators are quite close to the Borda voting rule [5,29,34]. In both cases the information provided by the individual sources generates a score (numerical evaluation) for each alternative, that are then aggregated using the sum.

There are some differences between the two processes. For the Borda voting rule the source provides a (linear) order. For belief merging, the source provides a belief base. The distance used to define the merging operator may produce a corresponding ordering, which is, in fact, a total preorder (we will see that this has an impact on the formal results).

But the similarity is large enough to warrant some deeper investigations. In particular, there are some interesting formal results on the Borda voting rule which we want to investigate in the belief merging context. This allows us to define two new families of belief merging operators and a characterization result.

Basically, there are two definitions for the Borda voting rule. These two definitions are equivalent when linear orders are considered. But it is no longer the case on general preorders. So we obtain two different definitions, that, applied to belief merging, give us new merging operators.

Another interesting formal result is that the Borda voting rule is characterized by a cancellation property [34]. This property is really about the orders, and cannot be directly translated to belief merging. But this idea can give us interesting counterparts. We investigate this class of cancellation properties. And we give a characterization of a belief merging operator using one of these properties.

We have to say that there is much work done on Borda rule. In particular, on adapting the Borda rule to incomplete preferences, see for instance [1,33]. However, our approach considering “all alternatives” (worlds) is closer to the classical Young’s approach.

The plan of the paper is as follows. The next Section provides the required notions and notations for the paper. Then in Section 3 we recall the definition of IC merging operators, the representation theorem in terms of plausibility preorders, and the definition of distance-based merging operators. In Section 4 we give the two definitions of the Borda voting rule, we show that they are not equivalent when preorders are used, and we give the cancellation property. In Section 5 we give the definition of the two families of Borda-like merging operators. These operators need a function that associates a preorder to each belief base. This can be provided, for instance, by an IC merging operator or by a belief revision operator. Then in Section 7 we investigate the properties of these two families of operators. And in Section 8 we investigate the cancellation properties and we provide a characterization of the $Δ^{d_{D}, f}$ operator and also of a family of merging operators in the style of Borda. For readability, some proofs of Sections 7 and 8 are in the Appendix. We conclude in Section 9.

2. Preliminaries

We consider a propositional language $L$ defined from a finite set of propositional variables $P$ and the standard connectives. An interpretation ω is a total function from $P$ to ${0, 1}$ . The set of all interpretations is noted Ω. An interpretation ω is a model of a formula $φ \in L$ if and only if it makes it true in the usual truth functional way. $⟦ φ ⟧$ denotes the set of models of the formula φ, i.e., $⟦ φ ⟧ = {ω \in Ω : ω ⊧ φ}$ . When M is a set of models, we denote by $φ_{M}$ a formula such that $⟦ φ_{M} ⟧ = M$ .

A profile E is a vector of formulae $E = (φ_{i_{1}}, \dots, φ_{i_{n}})$ where each $i_{j}$ represents an agent/individual/source (hence different agents/individuals/sources are allowed to exhibit identical formulae), so it represents a group of n agents. We denote by $E$ the set of profiles. $⋀ E$ represents the conjunction of formulae of $E = (φ_{i_{1}}, \dots, φ_{i_{n}})$ , i.e., $⋀ E = φ_{i_{1}} \land \dots \land φ_{i_{n}}$ . A profile E is said to be consistent if and only if $⋀ E$ is consistent. Two profiles $E_{1} = (φ_{i_{1}}, \dots, φ_{i_{n}})$ , $E_{2} = (φ_{j_{1}}, \dots, φ_{j_{n}})$ are equivalent, denoted $E_{1} \equiv E_{2}$ , if there is a bijective function σ from ${i_{1}, \dots, i_{n}}$ onto ${j_{1}, \dots, j_{n}}$ such that for every $i_{k} \in {i_{1}, \dots, i_{n}}$ , $φ_{i_{k}} \equiv φ_{σ (i_{k})}$ . The concatenation of profiles2

²
We assume that the profiles to be concatenated have disjoint sets of agents.

is noted ⊔. By abuse of notation we will write

φ ⊔ E

instead of

(φ) ⊔ E

. We denote by

E^{n}

the profile E “concatenated with itself n times”. More precisely

E^{n} = E_{1} ⊔ \dots ⊔ E_{n}

where each

E_{i}

is equivalent to E. The notation

\neg E

represents the profile composed of the negations of the belief bases of the profile

E = (φ_{i_{1}}, \dots, φ_{i_{n}})

, i.e.

\neg E = (\neg φ_{i_{1}}, \dots, \neg φ_{i_{n}})

A total preorder over a set X is a binary relation ≼ that is reflexive, transitive and total, ≺ and ≈ denotes the associated strict and the indifference relations respectively defined by $ω ≺ ω^{'}$ if and only if $ω ≼ ω^{'}$ and $ω^{'} ⋠ ω$ ; and $ω \approx ω^{'}$ if and only if $ω ≼ ω^{'}$ and $ω^{'} ≼ ω^{'}$ . Let ≼ be a total preorder on X, and $B \subseteq X$ , then $min (B, ≼) = {b \in B : ∄ x \in B, x ≺ b}$ .

If A is a set, we denote $| A |$ the cardinality of A. The symbol ⊆ will denote set containment and ⊂ strict set containment, i.e., $A \subset B$ if and only if $A \subseteq B$ and $A \neq B$ .

When ≼ is a total preorder over X, the canonical ranking function $r_{≼} : X \to N$ , associated to ≼ is defined by putting $r_{≼} (x)$ as the maximum of integers k such that there exists $x_{0}$ , $x_{1}, \dots$ , $x_{k}$ in X with $x_{k} = x$ and $x_{i} ≺ x_{i + 1}$ for $i = 0, \dots, k - 1$ .

Suppose $X = {x_{1}, \dots, x_{m}}$ . Given a vector $P = (≼_{1}, \dots, ≼_{n})$ of total preorders, we define $π_{i j} (P)$ , for any $i, j \in {1, \dots, m}$ , by $π_{i j} (P) = | {k \in {1, \dots, n} : x_{i} ≺_{k} x_{j}} |$ ; that is, $π_{i j} (P)$ represents the number of total preorders in the vector P which strictly prefer $x_{i}$ to $x_{j}$ . Note that $π_{i i} (P) = 0$ for any $i \in {1, \dots, m}$ , and that $\forall i, j \in {1, \dots, m}$ , $π_{i j} (P) ⩾ 0$ .

The merging operators we will consider are functions from the set of profiles and the set of propositional formulae (that will represent integrity constraints noted μ) to the set of formulae, i.e. $Δ : E \times L \to L$ . We will use the notation $Δ_{μ} (E)$ instead of $Δ (E, μ)$ . We write also $Δ (E)$ instead of $Δ_{⊤} (E)$ where ⊤ is a tautological formula.

3. IC merging

Let us recall in this Section the postulates for IC merging, the representation theorem, and the definition of distance-based operators [20].

Definition 1.
A merging operator Δ is called an IC merging operator if it satisfies postulates (IC0)–(IC8). An IC merging operator Δ is called a majority merging operator if it satisfies postulate (Maj). (IC0)
$Δ_{μ} (E) ⊧ μ$
(IC1)
If μ is consistent, then $Δ_{μ} (E)$ is consistent
(IC2)
If $⋀ E \land μ$ is consistent, then $Δ_{μ} (E) \equiv ⋀ E \land μ$
(IC3)
If $E_{1} \equiv E_{2}$ and $μ_{1} \equiv μ_{2}$ , then $Δ_{μ_{1}} (E_{1}) \equiv Δ_{μ_{2}} (E_{2})$
(IC4)
If $φ_{1} ⊧ μ$ , $φ_{2} ⊧ μ$ and $Δ_{μ} ((φ_{1}, φ_{2})) \land φ_{1}$ is consistent, then $Δ_{μ} ((φ_{1}, φ_{2})) \land φ_{2}$ is consistent
(IC5)
$Δ_{μ} (E_{1}) \land Δ_{μ} (E_{2}) ⊧ Δ_{μ} (E_{1} ⊔ E_{2})$
(IC6)
If $Δ_{μ} (E_{1}) \land Δ_{μ} (E_{2})$ is consistent, then $Δ_{μ} (E_{1} ⊔ E_{2}) ⊧ Δ_{μ} (E_{1}) \land Δ_{μ} (E_{2})$
(IC7)
$Δ_{μ_{1}} (E) \land μ_{2} ⊧ Δ_{μ_{1} \land μ_{2}} (E)$
(IC8)
If $Δ_{μ_{1}} (E) \land μ_{2}$ is consistent, then $Δ_{μ_{1} \land μ_{2}} (E) ⊧ Δ_{μ_{1}} (E) \land μ_{2}$
(Maj)
$\exists n ⩾ 1 Δ_{μ} (E_{1} ⊔ E_{2}^{n}) ⊧ Δ_{μ} (E_{2})$

Intuitively $Δ_{μ} (E)$ is a belief base close to the profile E satisfying the integrity constraints μ. This idea is what the postulates try to capture. The meaning of the postulates is the following: (IC0) ensures that the result of the merging satisfies the integrity constraints. (IC1) states that if the integrity constraints are consistent, then the result of the merging will be consistent. (IC2) states that if possible, the result of the merging is simply the conjunction of the belief bases with the integrity constraints. (IC3) is the principle of irrelevancy of syntax, i.e. if two profiles are equivalent and two integrity constraints are logically equivalent then the belief bases resulting of the two merging processes will be logically equivalent. (IC4) is the fairness postulate: the point is that when we merge two belief bases, merging operators must not give preference to one of them. (IC5) expresses the following idea: if two groups (profiles) $E_{1}$ and $E_{2}$ agree on some alternatives then these alternatives will be chosen if we join the two groups. (IC5) and (IC6) together state that if one could find two subgroups which agree on at least one alternative, then the result of the global merging will be exactly those alternatives the two groups agree on. (IC7) and (IC8) are a direct generalization of the (R5)–(R6) postulates for revision. They state that the notion of closeness is well-behaved (see [16] for a full justification). The postulate (Maj) expresses the fact that if a subgroup appears quite enough in the whole group then the opinion of the subgroup will prevail. In particular if an individual opinion has a large audience, it will be the opinion of the group.
Definition 2.
A function $E \mapsto ≼_{E}$ that maps each profile E to a total preorder over worlds $≼_{E}$ is called a syncretic assignment if: 1.
If $ω, ω^{'} ⊧ ⋀ E$ , then $ω \approx_{E} ω^{'}$
2.
If $ω ⊧ ⋀ E$ and $ω^{'} ⊭ ⋀ E$ , then $ω ≺_{E} ω^{'}$
3.
If $E_{1} \equiv E_{2}$ , then $≼_{E_{1}} = ≼_{E_{2}}$
4.
$\forall ω ⊧ φ_{1}$ , $\exists ω^{'} ⊧ φ_{2}$ , $ω^{'} ≼_{φ_{1} ⊔ φ_{2}} ω$
5.
If $ω ≼_{E_{1}} ω^{'}$ and $ω ≼_{E_{2}} ω^{'}$ , then $ω ≼_{E_{1} ⊔ E_{2}} ω^{'}$
6.
If $ω ≼_{E_{1}} ω^{'}$ and $ω ≺_{E_{2}} ω^{'}$ , then $ω ≺_{E_{1} ⊔ E_{2}} ω^{'}$
A syncretic assignment is called a majority assignment iff: 7.
If $ω ≺_{E_{2}} ω^{'}$ , then $\exists n$ , $ω ≺_{E_{1} ⊔ E_{2}^{n}} ω^{'}$

The first two conditions ensure that the models of the profile (if any) are the most plausible interpretations for the pre-order associated to the profile. The third condition states that two equivalent profiles have the same associated pre-orders. Those three conditions are very close to the ones existing in belief revision for faithful assignments [16]. The fourth condition states that, when merging two belief bases, for each model of the first one, there is a model of the second one that is at least as good as the first one. It ensures that the two knowledge bases are given the same consideration. The fifth condition says that if an interpretation ω is at least as plausible as an interpretation $ω^{'}$ for a profile $E_{1}$ and if ω is at least as plausible as $ω^{'}$ for a profile $E_{2}$ , then if one joins the two profiles, then ω will still be at least as plausible as $ω^{'}$ . The sixth condition strengthen the previous condition by saying that an interpretation ω is at least as plausible as an interpretation $ω^{'}$ for a knowledge set $E_{1}$ and if ω is strictly more plausible than $ω^{'}$ for a knowledge set $E_{2}$ , then if one joins the two knowledge sets, then ω will be strictly more plausible than $ω^{'}$ . These two previous conditions correspond to Pareto conditions in Social Choice Theory [3,17]. Condition seven says that if an interpretation ω is strictly more plausible than an interpretation $ω^{'}$ for a profile $E_{2}$ , then there is a quorum n of repetitions of the profile from which ω will be more plausible than $ω^{'}$ for the larger profile $E_{1} ⊔ E_{2}^{n}$ . This condition seems to be the weakest form of “majority” condition one could state.

Any IC merging operator can be represented by a syncretic assignment:
Theorem 1 ([20]).

A merging operator Δ is an IC merging operator (resp. majority merging operator) if and only if there exists a syncretic assignment (resp. majority assignment) that associates to every profile E a total preorder $≼_{E}$ such that for any formula μ, $⟦ Δ_{μ} (E) ⟧ = min (⟦ μ ⟧, ≼_{E})$ .

Remark 1.
An analysis of the proof of this theorem reveals that:
Postulates (IC0), (IC1), (IC7), (IC8) are enough to obtain the representation by an assignment $E \mapsto ≼_{E}$ where $≼_{E}$ is a total preorder over interpretations. When an operator satisfies (IC0), (IC1), (IC7), (IC8) we will say that it is representable.

Modulo the postulates mentioned in the previous point (which allow the representation) we have: (IC2) is equivalent to properties3
³
The properties are those of syncretic assignments (Definition 2).

1 and 2; (IC3) is equivalent to property 3; (IC4) is equivalent to property 4; (IC5) is equivalent to property 5; (IC6) is equivalent to property 6; (Maj) is equivalent to property 7.

It is not hard to see that when an operator Δ is representable, the assignment $E \mapsto ≼_{E}$ , representing it, is unique. Sometimes to refer to the unique assignment representing the operator Δ, we put $E \mapsto ≼_{E}^{Δ}$ to emphasize that it is precisely the assignment of this operator.

An interesting way to define concrete IC merging operators is to start from a distance d between worlds and an aggregation function f (see [22]), in order to construct a syncretic assignment, and then to use the equation in Theorem 1 for defining the operator. More precisely:
Definition 3.
Let $d : Ω \times Ω \to R$ and $f : ⋃_{n} R^{n} \to R$ be a distance4
⁴
Formally, only a pseudo-distance is required (triangle inequality is not necessary).

between worlds and an aggregation function respectively. Suppose that $E = (φ_{1}, \dots, φ_{n})$ is a profile.
$d (ω, φ_{i}) = {min}_{ω^{'} ⊧ φ_{i}} d (ω, ω^{'})$

$d^{f} (ω, E) = f_{φ_{i} \in E} {d (ω, φ_{i})}$

$ω ≼_{E}^{d, f} ω^{'}$ iff $d^{f} (ω, E) ⩽ d^{f} (ω^{'}, E)$
Given a profile E and a formula μ, the distance-based merging operator $Δ_{μ}^{d, f} (E)$ is defined as $⟦ Δ_{μ}^{d, f} (E) ⟧ = min (⟦ μ ⟧, ≼_{E}^{d, f})$ .

Usual distances are the drastic distance ( $d_{D} (ω, ω^{'}) = 0$ if $ω = ω^{'}$ and 1 otherwise), and the Hamming distance ( $d_{H} (ω, ω^{'}) = k$ if ω and $ω^{'}$ differ on k variables). Usual aggregation functions are the sum, the leximax, the sum of the n^th powers, the leximin etc. All these aggregation functions satisfy the properties that allow to obtain IC merging operators [18,22].

Actually, it is not hard to see that all the distances having two values have the same behavior when they are used for constructing merging operators. More precisely if $d_{1}$ and $d_{2}$ are two distances taking each of them two values (one of this values is necessarily 0), then $Δ_{μ}^{d_{1}, f} (E) \equiv Δ_{μ}^{d_{2}, f} (E)$ . For this reason, in this context, all the distances having two values will be identified with $d_{D}$ .

When the drastic distance $d_{D}$ is used, an important class of operators is obtained. More precisely, we have the following definition:
Definition 4.
An IC merging operator is called a drastic merging operator when it is of the form $Δ^{d_{D}, f}$ and $d_{D}$ is the drastic distance.

Actually these operators are all equivalent to $Δ^{d_{D}, Σ}$ , see Corollary 1.
4. Borda rules

We have deliberately chosen the plural in the title of this section because in Social Choice Theory there are two ways for defining the Borda rule. They are equivalent when the preferences of the voters are linear orders. But they are not necessarily equivalent if the preferences of the voters are total preorders as we will see below.

We recall some of the basic notions on social choice theory before introducing the Borda rules. From now on, $N = {1, 2, \dots, n}$ will denote a finite set of voters and $X = {x, y, z, \dots}$ will denote a finite set of alternatives. The ballot (or preference) of a voter i will be given by a total preorder $≼_{i}$ over X. The meaning of $x ≼_{i} y$ is that the agent i prefers the alternative x to the alternative y.5

⁵
We make this choice, converse to what is usually done in social choice, in order to be coherent with the orders used for belief revision.

A profile is an n-tuple

P = (≼_{1}, ≼_{2}, \dots, ≼_{n})

, which collects the ballots of all the voters in N, in an ordered manner. We will say that P is a linear profile if each

≼_{i}

in P is a linear order over X. A welfare choice function is a map W sending a profile P into a total preorder

≼_{P}

, the social preference associated to profile P.

Let us now define the scoring Borda rule:

Definition 5.

Given a profile $P = (≼_{1}, \dots, ≼_{n})$ on a set of alternatives $X = {x_{1}, \dots, x_{m}}$ and an alternative $a \in X$ , the borda score of a is the integer $r_{P}^{s} (a) = \sum_{i = 1}^{n} r_{≼_{i}} (a)$ . Now define $≼_{P}^{s}$ by putting $a ≼_{P}^{s} b$ if $r_{P}^{s} (a) ⩽ r_{P}^{s} (b)$ . Finally, the scoring Borda rule, $B^{s}$ , is the welfare choice function $B^{s} (P) = ≼_{P}^{s}$ .

Example 1.

Consider the set of alternatives $X = {x_{1}, x_{2}, x_{3}}$ and the following profile $P = (≼_{1}, ≼_{2})$ where $x_{1} ≺_{1} x_{2} ≃_{1} x_{3}$ and $x_{2} ≺_{2} x_{1} ≺_{2} x_{3}$ . It is easy to see that $r_{P}^{s} (x_{1}) = 1 = r_{P}^{s} (x_{2})$ and $r_{P}^{s} (x_{3}) = 3$ . Thus, $x_{1} ≃_{P}^{s} x_{2} ≺_{P}^{s} x_{3}$ .

Now we define the beta Borda rule (or comparison by pairs Borda rule).

Definition 6.

Let X be the set of alternatives ${x_{1}, \dots, x_{m}}$ . The score by comparison by pairs (β) of the alternative $x_{i}$ in the profile $P = (≼_{1}, \dots, ≼_{n})$ is defined as follows: $β_{i} (P) = \sum_{j = 1}^{m} (π_{i j} (P) - π_{j i} (P))$ .

When P is clear of the context we simply write $β_{i}$ instead of $β_{i} (P)$ .

Now we put $x_{i} ≼_{P}^{β} x_{j}$ if $β_{i} ⩾ β_{j}$ . Finally, the beta Borda rule $B^{β}$ is defined by putting $B^{β} (P) = ≼_{P}^{β}$ .

Example 2.

Consider $X = {x_{1}, x_{2}, x_{3}}$ and P as in Example 1. It is easy to see that $β_{1} (P) = 2$ , $β_{2} (P) = 1$ and $β_{3} (P) = - 3$ , that is $x_{1} ≺_{P}^{β} x_{2} ≺_{P}^{β} x_{3}$ .

We can now state that the two definitions are equivalent for linear orders, but not for general preorders. This result is known in social choice, and is mentioned in [34] but without proof. So we put it here for completeness.

Proposition 1.

For every linear profile P we have $B^{s} (P) = B^{β} (P)$ . This equality is not true in general, i.e. there exists a profile P such that $B^{s} (P) \neq B^{β} (P)$ .

Proof.

We observe that an alternative way to calculate $\sum_{j = 1}^{m} π_{i j} (P)$ is, for each $k \in {1, \dots, n}$ , to count the number of alternatives y such that $x_{i} ≺_{k} y$ and then make the sum of these numbers over $k \in {1, \dots, n}$ . Analogously, an alternative way to calculate $\sum_{j = 1}^{m} π_{j i} (P)$ is, for each $k \in {1, \dots, n}$ , count the number of alternatives y such that $y ≺_{k} x_{i}$ and then make the sum of these numbers over $k \in {1, \dots, n}$ . Note that if $≼_{k}$ is a linear order, the number of alternatives y such that $x_{i} ≺_{k} y$ is exactly $m - 1 - r_{≼_{k}} (x_{i})$ and the number of alternatives y such that $y ≺_{k} x_{i}$ is exactly $r_{≼_{k}} (x_{i}) - 1$ . Thus, $\sum_{j = 1}^{m} π_{i j} (P) = \sum_{k = 1}^{n} m - 1 - r_{≼_{k}} (x_{i}) = n m - n - r_{P}^{s} (x_{i})$ , $\sum_{j = 1}^{m} π_{j i} (P) = \sum_{k = 1}^{n} r_{≼_{k}} (x_{i}) - 1 = r_{P}^{s} (x_{i}) - n$ and $β_{i} = \sum_{j = 1}^{m} π_{i j} (P) - \sum_{j = 1}^{m} π_{j i} (P) = n m - 2 r_{P}^{s} (x_{i})$ . Therefore, $x_{i} ≼_{P}^{β} x_{j}$ iff $β_{i} ⩾ β_{j}$ iff $n m - 2 r_{P}^{s} (x_{i}) ⩾ n m - 2 r_{P}^{s} (x_{j})$ iff $r_{P}^{s} (x_{i}) ⩽ r_{P}^{s} (x_{j})$ iff $x_{i} ≼_{P}^{s} x_{j}$ .

The computations of Examples 1 and 2 show that $B^{s} (P) \neq B^{β} (P)$ . □

An interesting result by Young [34] is an axiomatic characterization of Borda rule for linear profiles. Let us introduce four axioms for a social welfare function6

⁶

A social welfare function is a map sending a profile of linear orders into a total preorder over alternatives.

Neutrality: For every permutation σ over the alternatives, $W (σ (P)) = σ (W (P))$ .

Faithfulness: For every singleton profile $(≼)$ , $W ((≼)) = ≼$ .

Consistency: Assume $P_{1}$ and $P_{2}$ are profiles over disjoint sets of voters. If $min (W (P_{1})) \cap min (W (P_{2})) \neq \emptyset$ , then $min (W (P_{1} ⊔ P_{2})) = min (W (P_{1})) \cap min (W (P_{2}))$ .

Cancellation: If for every pair of alternatives $x_{i}$ , $x_{j}$ we have $π_{i j} (P) = π_{j i} (P)$ then $W (P)$ is the flat total preorder.7

⁷

The flat total preorder over X, is the unique total preorder ≼ such that for all x, y in X, we have $x ≼ y$ .

Theorem 2 ([34]).

Restrained to linear profiles, the only social welfare function satisfying neutrality, faithfulness, consistency and cancellation is the Borda rule $B^{s}$ .

So on linear profiles the two definitions of Borda rules coincide, and this rule is characterized exactly by those four axioms.

5. Borda-like merging

In this section we will use the two definitions of the previous section (which we know, from Proposition 1, differ in the general case) in order to define merging operators. We just need a generating function that associates a total preorder on interpretations to any base φ:

Definition 7.
We call generating function any function ⊲ that associates to each belief base φ a total preorder on interpretations $≼_{φ}$ such that $min (Ω, ≼_{φ}) = ⟦ φ ⟧$ and $≼_{φ} = ≼_{φ^{'}}$ whenever $φ \equiv φ^{'}$ .

Note that ⊲ can be provided by a revision operator ∘ or a merging operator Δ since, from the representation theorems in terms of faithful/syncretic assignments, they allow to associate a preorder to each belief base φ. In particular, we denote $⊲_{△}$ the generating function associated to Δ, that is $⊲_{△} (φ) = ≼_{φ}^{Δ}$ . Note that a distance d between interpretations is also a manner to define a preorder for each belief base φ, with $ω ≼_{φ} ω^{'}$ if and only if $d (ω, φ) ⩽ d (ω^{'}, φ)$ .

Once a generating function ⊲ is considered, it is easy to associate to a profile of belief bases E, a profile $P_{E}^{⊲}$ of preorders over Ω (the elements of Ω are viewed as alternatives). More precisely, given $E = (φ_{1}, \dots, φ_{n})$ , we put $P_{E}^{⊲} = (≼_{φ_{1}}, \dots, ≼_{φ_{n}})$ where $≼_{φ_{i}} = ⊲ (φ_{i})$ for $i = 1, \dots, n$ .
Definition 8.
Given a generating function ⊲ and a profile $P_{E}^{⊲} = (≼_{φ_{1}}, \dots, ≼_{φ_{n}})$ over Ω associated to $E = (φ_{1}, \dots, φ_{n})$ with ⊲, we consider the assignment $P_{E}^{⊲} \mapsto ≼_{P_{E}^{⊲}}^{β}$ (see Definition 6). The β-Borda merging operator $Δ^{β_{⊲}}$ is defined by: $\begin{matrix} ⟦ Δ_{μ}^{β_{⊲}} (E) ⟧ = min (⟦ μ ⟧, ≼_{P_{E}^{⊲}}^{β}) \end{matrix}$

We say that a merging operator is based on pairwise comparison if it is identical to its β-Borda merging version:
Definition 9.
Let Δ be a merging operator and $⊲_{△}$ the generating function associated to Δ. We say that Δ is based on pairwise comparisons iff $Δ = Δ^{β_{⊲_{△}}}$ .

In an analogous way, using the scoring Borda welfare function $B^{s}$ of Definition 5, we can define another merging operator, which transforms each preorder into a score function for each base, and the score of an interpretation is the sum of all its scores. This way to proceed can be related to the usual $Δ^{d, Σ}$ operators, but instead of using a distance, we use a more qualitative information provided by the preorder:
Definition 10.
Given a generating function ⊲, a profile $P_{E} = (≼_{φ_{1}}, \dots, ≼_{φ_{n}})$ over Ω associated to $E = (φ_{1}, \dots, φ_{n})$ with ⊲, we consider the assignment $E \mapsto ≼_{P_{E}}^{s}$ (see Definition 5). The s-Borda merging operator $Δ^{s_{⊲}}$ is defined by: $\begin{matrix} ⟦ Δ_{μ}^{s_{⊲}} (E) ⟧ = min (⟦ μ ⟧, ≼_{P_{E}}^{s}) \end{matrix}$

We say that a merging operator is an s-Borda operator if it is identical to its s-Borda merging version, more precisely: Definition 11.
Let Δ be a merging operator and $⊲_{△}$ the generating function associated to Δ. We say that Δ is an s-Borda merging operator iff $Δ = Δ^{s_{⊲_{△}}}$ .

6. Example

In this section we provide an example for illustrating the difference of behaviour between β-Borda operators, s-Borda operators and classical distance-based merging operators.

Consider the profile $E = (φ_{1}, φ_{2}, φ_{3})$ , with $⟦ φ_{1} ⟧ = {111, 001}$ , $⟦ φ_{2} ⟧ = {011, 110}$ , and $⟦ φ_{3} ⟧ = {000}$ . We do not consider any integrity constraint, so $μ = ⊤$ .

We will consider the distance-based merging operator $Δ^{d_{H}^{ρ}, Σ}$ , that is, the operator for which the sum is the aggregation function, and the distance is the weighted Hamming distance $d_{H}^{ρ}$ , defined below:

Definition 12.
Let $ρ : P \to R^{*}$ be a function that associates to any propositional variable in the language a strictly positive weight. Then the weighted-Hamming distance $d_{H}^{ρ}$ between two interpretations ω and $ω^{'}$ is defined as: $\begin{matrix} d_{H}^{ρ} (ω, ω^{'}) = \sum_{x \in P, ω (x) \neq ω^{'} (x)} ρ (x) \end{matrix}$

Using such a distance is very natural when all propositional variables do not have the same importance. Such is the case if the base can be split in several topics (encoded by subsets of propositional variables), with some topics being more important than others.

Note that the standard Hamming distance is obtained in the particular case where all weights are equal to 1.

In this example we will use the weight function $ρ = (1, 3, 6)$ . And we will look at the results of the merging of the profile E for the operator $Δ^{d_{H}^{ρ}, Σ}$ , for its s-Borda and β-Borda versions where the generating function is the one associated to the operator $Δ^{d_{H}^{ρ}, Σ}$ . In order to simplify the notation we call ◀ this generating function, that is, $◀ = ⊲_{Δ^{d_{H}^{ρ}, Σ}}$ .

Table 1
Computation of $Δ^{d_{H}^{ρ}, Σ} (E)$ : in the three first columns appear the weighted distances. The fourth column is the sum of weighted distances. The row in gray corresponds to model which minimizes the sum. Thus, $⟦ Δ^{d_{H}^{ρ}, Σ} (E) ⟧ = {001}$

Table 2
Computation of $Δ^{s_{◀}} (E)$ : in the three first columns appear the ranks of the interpretations in $≼_{φ_{i}}$ , that is, $◀ (φ_{i})$ . The fourth column is the Borda score. The rows in gray corresponds to models which minimize the Borda score. Thus, $⟦ Δ^{s_{◀}} (E) ⟧ = {000, 110}$

Table 3
Computation of $Δ^{β_{◀}} (E)$ : in the first column appears the sum of the number of models less preferred than the i-th model. In the second column appears the sum of the number of models preferred to the i-th model. The fourth column is the $β_{i}$ score, that is, the difference between the two first columns. The row in gray corresponds to model which minimize the $β_{i}$ score. Thus, $⟦ Δ^{β_{◀}} (E) ⟧ = {110}$

Tables 1, 2, 3 sum up the respective computations. Then, one can check that the result for the distance-based operator is $⟦ Δ^{d_{H}^{ρ}, Σ} (E) ⟧ = {001}$ . Whereas for its s-Borda version the exact values of the distance are not used, just the plausibility order from each base is considered, that leads us to a different result: $⟦ Δ^{s_{◀}} (E) ⟧ = {000, 110}$ . Finally, using the β-Borda version of this operator, we compute the relative positions of all couples of interpretations via the $β_{i}$ , and we obtain as result: $⟦ Δ^{β_{◀}} (E) ⟧ = {110}$ .

Finally, let us note that there is not, in general, a logical correlation between the operators $Δ^{d_{H}^{ρ}, Σ}$ , $Δ^{s_{◀}}$ and $Δ^{β_{◀}}$ . In this example we can already see that this is the case between $Δ^{d_{H}^{ρ}, Σ}$ and the two other operators, but we have $Δ^{β_{◀}} (E) ⊢ Δ^{s_{◀}} (E)$ . To see that it is not always the case let us do the merging under the constraints $⟦ μ ⟧ = {010, 111}$ . From Tables 2 and 3 we can easily see that $⟦ Δ_{μ}^{s_{◀}} (E) ⟧ = {010}$ and $⟦ Δ_{μ}^{β_{◀}} (E) ⟧ = {111}$ Thus, in general, it is not the case that $Δ_{μ}^{s_{◀}} (E) ⊢ Δ_{μ}^{β_{◀}} (E)$ nor $Δ_{μ}^{β_{◀}} (E) ⊢ Δ_{μ}^{s_{◀}} (E)$ .
7. Properties of Borda-like merging

We will now study the logical properties of the two above-defined families of operators.

First we can show that s-Borda merging operators satisfy all IC merging postulates except (IC4). This fact is a direct consequence of a result of [20]:

Proposition 2.
A merging operator $Δ^{s_{⊲}}$ satisfies (IC0)–(IC3) and (IC5)–(IC8).

So we obtain all the usual rationality postulates except (IC4) which requires some symmetry between the bases, that we can not ensure here.

Now note that we obtain the same result for β-Borda operators:
Proposition 3.
A merging operator $Δ^{β_{⊲}}$ satisfies (IC0)–(IC3) and (IC5)–(IC8).

This definition of β-Borda (pairwise comparison) operators allows us to provide a characterization of the drastic merging operator.
Theorem 3.
Let $Δ^{d, f}$ be a distance-based operator. $Δ^{d, f}$ is based on pairwise comparisons if and only if it is the drastic operator.

So the drastic merging operator is the only operator in the class of distance-based operators to be identical to its β-Borda version (i.e. to be a pairwise comparison operator). In the next section we will show a more general characterization of this drastic merging operator.
8. Cancellation

In this section we would like to introduce and discuss the notion of cancellation in belief merging.

In the characterization of the Borda rule, the cancellation property can be interpreted as requiring that a relation $a < b$ between two alternatives, can be cancelled by the converse relation $b < a$ (given by another individual). Please look at the formal definition of cancellation given in Section 4.

We will now explore this general idea in order to define cancellation properties in belief merging. The idea is to state that a base in the profile can be cancelled by some other input. The exact definition of the “other input” will lead us to different cancellation properties.

Definition 13.
A merging operator Δ satisfies the ( $\neg φ$ -Can) property if for every formula φ, and every integrity constraint μ, ( $\neg φ$ -Can)
$Δ_{μ} (φ ⊔ \neg φ) \equiv μ$

It is easy to verify the following:
Proposition 4.
Let Δ be an IC merging operator. Then Δ satisfies ( $\neg φ$ -Can) if and only if it satisfies ( $\neg E$ -Can) ( $\neg E$ -Can)
$\forall E, \forall μ Δ_{μ} (E ⊔ \neg E) \equiv μ$

Now we can provide a characterization of the drastic merging operator $Δ^{d_{D}, f}$ in terms of cancellation:
Theorem 4.
An IC merging operator Δ satisfies the ( $\neg φ$ -Can) cancellation property if and only if $Δ = Δ^{d_{D}, f}$ .

In fact, after a careful reading of the proof, one can see that Theorem 4 may be expressed in a more general way. To make this Theorem true, we need:

a generating function ⊲

an assignment associated with the merging process, satisfying Condition 6 of the syncretic assignment.

We know that a distance d between interpretations is a way to define a generating function, as it defines naturally a preorder on interpretations. So an interesting question arises about the expression of Theorem 4 when a distance d and an aggregation function f are available.
Proposition 5.
If the aggregation function f is anonymous and not decreasing, the merging operator $Δ^{d, f}$ satisfies the ( $\neg φ$ -Can) cancellation property if and only if $d = d_{D}$ .
Proof.
Suppose that a merging operator $Δ^{d, f}$ satisfies the ( $\neg φ$ -Can) property, and that $d \neq d_{D}$ .

As $d \neq d_{D}$ , there is at least one base k and three interpretations $ω_{1}$ , $ω_{2}$ , $ω_{3}$ such that $ω_{1} ⊧ k$ , $ω_{2} ⊭ φ$ , $d (ω_{1}, ω_{2})$ is minimal among all the interpretations of $\neg φ$ (i.e. $d (ω_{1}, ω_{2}) = {min}_{ω_{k} ⊧ \neg φ} (d (ω_{1}, ω_{k}))$ ) and $d (ω_{2}, φ) < d (ω_{3}, φ)$ .

Consider $E = ⟨ φ_{ω_{1}}, φ_{\neg ω_{1}} ⟩$ . By the ( $\neg φ$ -Can) property, $Δ (⟨ φ_{ω_{1}}, φ_{\neg ω_{1}} ⟩) \equiv ⊤$ , so $ω_{3} ≃_{E} ω_{1}$ .

But as $0 = d (ω_{1}, φ) < d (ω_{2}, φ) < d (ω_{3}, φ)$

And $0 = d (ω_{2}, φ_{\neg ω_{1}}) = d (ω_{3}, φ_{\neg ω_{1}}) < d (ω_{1}, φ)$ .

As $d (ω_{1}, ω_{2}) = {min}_{ω_{k} ⊧ \neg φ} (d (ω_{1}, ω_{k})) = d (ω_{1}, φ_{\neg ω_{1}})$ , and $d (ω_{1}, ω_{2}) = d (ω_{2}, φ_{ω_{1}})$ , we have $d (ω_{1}, φ_{\neg ω_{1}}) = d (ω_{2}, φ_{ω_{1}})$ .

As the aggregation function f is not decreasing and anonymous, $d (ω_{1}, {φ_{ω_{1}}, φ_{\neg ω_{1}}}) = d (ω_{2}, {φ_{ω_{1}}, φ_{\neg ω_{1}}}) < d (ω_{3}, {φ_{ω_{1}}, φ_{\neg ω_{1}}})$

This contradicts $Δ (φ_{ω_{1}} ⊔ φ_{\neg ω_{1}}) \equiv ⊤$ . □

We can stress that in Proposition 5, no assumption is made on the assignment associated with $Δ^{d, f}$ . In particular, we do not suppose that $Δ^{d, f}$ is an IC merging operator.

The ( $\neg φ$ -Can) cancellation property is interesting for obtaining the above characterization, but it is a very particular instance of a larger family of cancellation properties that we would like to introduce and discuss now, and that could lead to other characterization results.

First we introduce two postulates of cancellation that share the fact that a base can be cancelled by another base.
Definition 14 (Cancellation 1).

( $\neg φ$ -Can)

$\forall φ, \forall μ Δ_{μ} (φ ⊔ \neg φ) \equiv μ$

( φ -Can)

$\forall φ, \exists φ^{'}, \forall μ Δ_{μ} (φ ⊔ φ^{'}) \equiv μ$

We begin by ( $\neg φ$ -Can), which we already defined above. Note that this is a particular case, using negation, of the (φ-Can) postulate, which states that any base can be cancelled by another base.

Yet, we can be a bit more general, and accept that maybe a single base will not be enough to cancel any base, and that a set of such bases will be necessary. This leads to other group of possible postulates:

Definition 15 (Cancellation 2).

(E-Can)

$\forall φ$ , $\exists E$ , $\forall μ Δ_{μ} (φ ⊔ E) \equiv μ$

(fE-Can)

$\forall φ$ , $\exists E$ such that $f (E)$ and $\forall μ Δ_{μ} (φ ⊔ E) \equiv μ$

(

\neg ω

-Can)

$\forall φ$ , $\exists E$ such that $(\forall ψ \in E \exists ω_{i} ψ = φ_{\neg ω_{i}})$ and $\forall μ Δ_{μ} (φ ⊔ E) \equiv μ$

(

\neg ω^{n}

-Can)

$\forall φ$ if $E = ⨆_{i} {(φ_{\neg ω_{i}})}^{r_{≼_{φ}} - r_{≼_{φ}} (ω_{i})}$ then $\forall μ Δ_{μ} (φ ⊔ E) \equiv μ$

The most general form of these cancellation postulates is (E-Can) which states that some set of bases can cancel a chosen base. Then (fE-Can) is a restriction, where E cannot be chosen freely, but must satisfy some condition $f ()$ . One such interesting restriction is given by ( $\neg ω$ -Can) where all the bases of E have to be negations of a complete base $φ_{ω}$ . We further specialize this last postulate and obtain ( $\neg ω^{n}$ -Can) that gives the exact definition of the profile E corresponding to a given base φ. This last form is related to s-Borda operators.

Let us note that all these postulates can be generalized for profiles not composed of a single base, but only in this work we treat these more simple forms. Let us just give the result for (E-Can) (but then notice that we can prove a similar result for all the other cancellation postulates):

Proposition 6.
Let Δ be an IC merging operator. Then Δ satisfies (E-Can) if and only if Δ satisfies (E-CanE) (E-CanE)
$\forall E^{'}, \forall φ, \exists E Δ_{μ} (E^{'} ⊔ φ ⊔ E) \equiv Δ_{μ} (E^{'})$

Clearly some of the above postulates are more general than others:
Proposition 7.
We have the relation of Fig. 1 , where $X \to Y$ means that Y is more general than X (i.e. if Δ satisfies X then it satisfies Y).
Fig. 1.
Cancellation postulates.

We let the exploration of the different forms of Cancellation for future work. However we finish this section by giving an important result which shows tight links between s-Borda merging operators and ( $\neg ω^{n}$ -Can).
Theorem 5.
Let Δ be an operator that satisfies (IC0)–(IC3) and (IC5)–(IC8). Δ is a s-Borda merging operator if and only if Δ satisfies ( $\neg ω^{n}$ -Can) .

We put in gray in Fig. 1 the two Cancellation postulates for which we have some links with concrete merging operators. We are convinced that further exploration of these links can provide us with other interesting characterizations of operators.
9. Conclusion

In this paper, we defined two families of merging operators inspired by the definition of the Borda voting rule. We also introduced the notion of cancellation in belief merging, inspired by the axiomatization of the Borda voting rule proposed by Young. This allowed us to show that the drastic merging operator is the only IC merging operator satisfying one variant of Cancellation, which gave us a characterization of this operator. We have also characterized the s-Borda merging operators as the operators satisfying another variant of Cancellation ( $\neg ω^{n}$ -Can). We are convinced that a more systematic exploration of the other variants of Cancellation proposed by us (or other ones) can lead us to other interesting characterizations of belief merging operators.

Footnotes

Some proofs

The proof of Proposition 4 is based in the following useful lemma:

In order to give the proof of Theorem 5 are going to establish some lemmas which will be useful therein.

Acknowledgements

This work has benefited from the support of the AI Chair BE4musIA of the French National Research Agency (ANR-20-CHIA-0028). The fourth author has been partially funded by the program PAUSE of Collège de France.

We would like to especially thank the reviewers of the French version that appeared at JIAF 2022 for their valuable comments and suggestions that have contributed to improving this work.

References

Ackerman,

Choi,

Coughglin,

Gottlieb and

Wood, Elections with partially ordered preferences, Public Choice157 (2013), 145–168. doi:10.1007/s11127-012-9930-3.

C.E.

Alchourrón,

Gärdenfors and

Makinson, On the logic of theory change: Partial meet contraction and revision functions, Journal of Symbolic Logic50 (1985), 510–530. doi:10.2307/2274239.

K.J.

Arrow, Social Choice and Individual Values, 2nd edn, Wiley, New York, 1963.

K.J.

Arrow,

A.K.

Sen and

Suzumura, eds, Handbook of Social Choice and Welfare, Vol. 1, North-Holland, 2002.

J.C.

Borda, Mémoire sur les élections au scrutin, Histoire de l’Académie Royale des Sciences (1781).

Dietrich, Scoring rules for judgment aggregation, Social Choice and Welfare42 (2014), 873–911. doi:10.1007/s00355-013-0757-8.

Duddy,

Piggins and

W.S.

Zwicker, Aggregation of binary evaluations: A Borda-like approach, Soc. Choice Welf.46(2) (2016), 301–333. doi:10.1007/s00355-015-0914-3.

Everaere,

Konieczny and

Marquis, The strategy-proofness landscape of merging, Journal of Artificial Intelligence Research28 (2007), 49–105. doi:10.1613/jair.2034.

Everaere,

Konieczny and

Marquis, The epistemic view of belief merging: Can we track the truth? in: Nineteenth European Conference on Artificial Intelligence (ECAI’10), 2010, pp. 621–626.

10.

Everaere,

Konieczny and

Marquis, Disjunctive merging: Quota and Gmin merging operators, Artificial Intelligence174 (12–13) 2010, 824–849.

11.

Everaere,

Konieczny and

Marquis, On egalitarian belief merging, in: Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR’14), 2014.

12.

Everaere,

Konieczny and

Marquis, Counting votes for aggregating judgments, in: International Conference on Autonomous Agents and Multi-Agent Systems, (AAMAS’14), Paris, France, May 5–9, 2014, 2014, pp. 1177–1184.

13.

Everaere,

Konieczny and

Marquis, Belief merging versus judgment aggregation, in: Fourteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS’15), 2015, pp. 999–1007.

14.

Fermé and

S.O.

Hansson, AGM 25 years: Twenty-five years of research in belief change, Journal of Philosophical Logic40(2) (2011), 295–331. doi:10.1007/s10992-011-9171-9.

15.

Gärdenfors, Knowledge in Flux, MIT Press, 1988.

16.

Katsuno and

A.O.

Mendelzon, Propositional knowledge base revision and minimal change, Artificial Intelligence52 (1991), 263–294. doi:10.1016/0004-3702(91)90069-V.

17.

J.S.

Kelly, Arrow Impossibility Theorems, Series in Economic Theory and Mathematical Economics, Academic Press, New York, 1978.

18.

Konieczny,

Lang and

Marquis, DA² merging operators, Artificial Intelligence157 (2004), 49–79. doi:10.1016/j.artint.2004.04.008.

19.

Konieczny and

Pino Pérez, On the logic of merging, in: Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR’98), 1998, pp. 488–498.

20.

Konieczny and

Pino Pérez, Merging information under constraints: A logical framework, Journal of Logic and Computation12(5) (2002), 773–808. doi:10.1093/logcom/12.5.773.

21.

Konieczny and

Pino Pérez, Propositional belief base merging or how to merge beliefs/goals coming from several sources and some links with social choice theory, European Journal of Operational Research160(3) (2005), 785–802. doi:10.1016/j.ejor.2003.06.039.

22.

Konieczny and

Pino Pérez, Logic based merging, Journal of Philosophical Logic40(2) (2011), 239–270. doi:10.1007/s10992-011-9175-5.

23.

Lang,

Pigozzi,

Slavkovik,

van der Torre and

Vesic, A partial taxonomy of judgment aggregation rules and their properties, Social Choice and Welfare48(2) (2017), 327–356. doi:10.1007/s00355-016-1006-8.

24.

Liberatore and

Schaerf, Arbitration (or how to merge knowledge bases), IEEE Transactions on Knowledge and Data Engineering10(1) (1998), 76–90. doi:10.1109/69.667090.

25.

Lin and

A.O.

Mendelzon, Merging databases under constraints, International Journal of Cooperative Information System7(1) (1998), 55–76. doi:10.1142/S0218843098000040.

26.

List and

Pettit, Aggregating sets of judgments. An impossibility result, Economics and Philosophy18 (2002), 89–110. doi:10.1017/S0266267102001098.

27.

List and

Puppe, Judgment aggregation: A survey, in: The Handbook of Rational and Social Choice, Oxford University Press, 2009.

28.

Mata Díaz and

Pino Pérez, Impossibility in belief merging, Artificial Intelligence251 (2017), 1–34. doi:10.1016/j.artint.2017.06.003.

29.

Merlin, The axiomatic characterizations of majority voting and scoring rules, Mathématiques et sciences humaines41 (2003), 87–109.

30.

Pigozzi, Belief merging and the discursive dilemma: An argument-based account to paradoxes of judgment aggregation, Synthese152(2) (2006), 285–298. doi:10.1007/s11229-006-9063-7.

31.

Pigozzi, Belief merging and judgment aggregation, in: The Stanford Encyclopedia of Philosophy (Spring 2021 Edition),

E.N.

Zalta, ed., 2021, https://plato.stanford.edu/archives/spr2021/entries/belief-merging/ .

32.

P.Z.

Revesz, On the semantics of arbitration, International Journal of Algebra and Computation7(2) (1997), 133–160. doi:10.1142/S0218196797000095.

33.

Terzopoulou and

Endriss, The Borda class: An axiomatic study of the Borda rule on top-truncated preferences, Journal of Mathematical Economics92 (2021), 31–40. doi:10.1016/j.jmateco.2020.11.001.

34.

H.P.

Young, An axiomatization of Borda’s rule, Journal of Economic Theory9 (1974), 43–52. doi:10.1016/0022-0531(74)90073-8.

On the links between belief merging,the Borda voting method,and the cancellation property 1

Abstract

Keywords

1. Introduction

2. Preliminaries

2 We assume that the profiles to be concatenated have disjoint sets of agents.

5 We make this choice, converse to what is usually done in social choice, in order to be coherent with the orders used for belief revision.

5. Borda-like merging

Definition 15 (Cancellation 2).

Footnotes

Some proofs

Acknowledgements

References

²
We assume that the profiles to be concatenated have disjoint sets of agents.

⁵
We make this choice, converse to what is usually done in social choice, in order to be coherent with the orders used for belief revision.