\section{Framework}


In this section we introduce our formal framework to represent judgment aggregation problems. A set of agents $N=\{1, 2, \ldots, n\}$ makes judgments on logically interconnected propositions. The set $\mathcal{P}$ of atomic propositions is defined as the union of two disjoint sets:  $\mathcal{P}_p$ containing variables $a,b,c, \ldots, p,q$ for the premises, and $\mathcal{P}_c$ being a singleton $\{x\}$, where $x$ is the variable for the conclusion. We assume that the conclusion is an atomic formula. $\mathcal{L}$ is a language built from $\mathcal{P}$, 
including complex formulas as $\neg a, (a \wedge~b), (a \vee~b), (p \to~q), (a \leftrightarrow~p)$.

The set of issues on which the judgments have to be made is called \textit{agenda} and is denoted by $\Phi \subseteq \mathcal{L}$. The agenda is assumed to be finite and closed under negation: if $a \in \Phi $, then $\neg a \in \Phi$.\footnote{To increase readability, in the tables we list only the positive issues, and assume that, for any issue in the agenda, an individual deems that issue to be true if and only if she deems its negation to be false.} Each double negated proposition $\neg \neg a$ is identified with its corresponding non negated proposition $a$. We split the agenda in two parts: one containing the premises ($\Phi_p$), and one containing the conclusion ($\Phi_c$). We exclude agenda items such as $a \to x$, i.e. formulas containing premises and conclusion. Our procedure consists of two different aggregations: one on the individual judgments on $\Phi_p$ and one on the individual judgments on $\Phi_c$.


A subset $J \subseteq \Phi$ is the \textit{collective judgment set} and contains the set of propositions believed by the group. Similarly, we define individual $i$'s judgment set $J_i \subseteq \Phi$. A collective judgment set is \textit{consistent} if it is a consistent set in $\mathcal{L}$, and is \textit{complete} if, for any $a \in \mathcal{L}$, $a \in J$ or $\neg a \in J$ (consistent and complete individual judgment sets are defined in the same way). We only consider consistent complete judgment sets. 

A \textit{decision rule} $\mathcal{R}$ is a formula of $\mathcal{L}$ that represents the logical connections between premises and conclusion. More precisely, $\mathcal{R}$ has the form $\Psi \leftrightarrow x$, where $\Psi \in \mathcal{L} / \{x\}$. The decision rule is not an item of the agenda. This means that the group members do not vote on $\mathcal{R}$, but each individual is required to give judgments that satisfy the given rule.

 

Like the agenda, each judgment set is split in two disjoint  subsets: $J_{i,p}$ and $J_{i,c}$.  The first is the individual $i$'s  
judgment set on the premises, and $J_{i,c}$ is the individual $i$'s  judgment set on the conclusion. The collective judgment sets on  
premises and conclusion will be denoted respectively by $J_p$ and $J_c $. 

We say that a premise $a$ (resp. a conclusion $x$) is \textit{unanimously supported} if $a \in J_{i,p}$ for all $J_{i,p} \subseteq \Phi$ (resp. $x \in J_{i,c}$ for all $J_{i,c} \subseteq \Phi$).

A \textit{profile} $\underline{J}$ is an $n$-tuple $(J_1, J_2, \ldots, J_n)$ of agents' judgment sets. An \textit{aggregation rule} $F$ assigns a set of collective judgment sets $J$ to each profile $\underline{J}$. For our procedure we need to define two aggregation rules: one for the aggregation of the individual premises and one for the conclusion. To relate the two aggregation rules, we have a set of integrity constraints $IC$. $IC$ indicates the set of admissible interpretations, i.e.  the admissible collective  judgment sets. Also, to allow for situations in which the aggregated judgment set is not unique, i.e. there are ties, we aggregate the profiles into {\em sets} of aggregated judgment sets.



A \textit{premise profile} $\underline{J_p}$ is an $n$-tuple $(J_{1,p}, J_{2,p}, \ldots, J_{n,p})$ of agents' judgment sets on premises. A \textit{premise aggregation rule}   
 $F_{IC}$ assigns a set of collective judgment sets $J_p$ to each premise profile $(J_{1,p}, J_{2,p}, \ldots, J_{n,p})$ and set of integrity constraints $IC$. Conclusion profiles $(J_{1,c}, J_{2,c}, \ldots, J_{n,c})$ and conclusion aggregation rules $F_c$ are defined similarly.


\subsection{Complete conclusion-based procedure}\label{proc}
\label{ccbp}
Each individual provides, simultaneously, the set of premises and conclusion that she believes. Our two-step procedure first performs a standard CBP, i.e. it aggregates the individual judgments on the conclusion by majority rule. This means that $x$ (resp. $\neg x$) is the collective conclusion iff there are at least $\lfloor\frac{n}{2}\rfloor +1$ agents voting for $x$ (resp. $\neg x$). The second step consists in determining the set of reasons which support the collective conclusion. This is done by applying a \textit{distance-based merging operator} to $J_{i,p}$. 

 

Distance minimization merging procedures have been already applied to judgment aggregation problems \cite{Pigozzi2006}. In this section we briefly present a majority merging operator with integrity constraints following \cite{KPP02,KLM2004}. 
Unlike in \cite{KPP02,KLM2004}, when the merging operator outputs ties, we take the disjunction of the formulas which completely characterize the tied alternatives.

An \textit{interpretation} is a function $v: \mathcal{P} \to \{0,1\}$ and it is represented as the list of the binary evaluations. For example, given three propositional variables $a$, $b$ and $c$, the vector (0,1,0) stands for the interpretation in which $a$ and $c$ are false and $b$ is true. Let $\mathcal{W}=\{0,1\}^{\mathcal{P}}$ be the set of all interpretations. An interpretation is a \textit{model} of a propositional formula if and only if it makes the formula true in the usual truth functional way. 

Let us suppose that $\Phi_p = \{a,\neg a, b, \neg b, c, \neg c\}$, and that agent 1 believes that $a, \neg b$ and $\neg c$, i.e.  $J_{1,p}= \{a, \neg b, \neg c\}$. We represent $J_{1,p}$ as a 0-1 vector of length equal to the number of propositions in $J_{1,p}$, i.e. $(1,0,0)$. Suppose also that $\mathcal{R}= ((a \vee b) \wedge c) \leftrightarrow x$ and that, unlike agent 1, the majority of the individuals voted in favor of $x$. Hence, the first step of our procedure sets $v(x)=1$. We now want to define an aggregation on $J_{i,p}$ such that the collective judgment set on the premises is one of the models of $((a \vee b) \wedge c) \leftrightarrow x$ where $v(x)=1$. This means that $J_{p}$ must be one of the following interpretations: (1,1,1), (0,1,1), (1,0,1). The set of premises supporting the collective conclusion will constrain the aggregation procedure on $J_{i,p}$. 

Given a premise profile $\underline{J_p}$ and $IC$, $F_{IC}(\underline{J_p})$ denotes a set of collective judgment sets on the premises resulting from the $IC$ merging on $\underline{J_p}$. The idea of a distance minimization merging operator is that $F_{IC}(\underline{J_p})$ will select those interpretations in $IC$, which are at minimal distance from $\underline{J_p}$. A distance $d(\omega,\underline{J_p})$ between an interpretation $\omega$ and the premise profile $\underline{J_p}$ induces a total pre-order ($\leq$) on the interpretations.

In order to obtain the total pre-order on the interpretations, we first need to determine a pseudo-distance between each admissible interpretation and each $J_{i,p}$. Then, we need to aggregate all these values in order to obtain a pseudo-distance value between an interpretation and $\underline{J_p}$. Let us see this in detail (we follow \cite{KPP02,KLM2004}).

A pseudo-distance between interpretations is a function $d: \mathcal{W}\times \mathcal{W} \rightarrow\mathbb{R}_{+}$ such that for all $\omega,\omega^{\prime}\in\mathcal{W}$: $d(\omega,\omega^{\prime})=d(\omega^{\prime},\omega)$ and $d(\omega,\omega^{\prime})=0$ iff $\omega=\omega^{\prime}$.


A pseudo-distance between an interpretation $\omega$ and  $\underline{J_p}$ is defined with the help of an aggregation function $D$: $\mathbb{R}_{+}^{n}\rightarrow\mathbb{R}_{+}$ as $D^{d}(\omega, \underline{J_p})$=$D\left(d(\omega,J_{1,p}),\ldots ,d(\omega,J_{n,p})\right)$ \cite{KLM2004}. 
Any such aggregation function induces a total pre-order $\leqslant_{\underline{J_p}}$ on the set $\mathcal{W}$ with respect to the pseudo-distances to a given $\underline{J_p}$. Thus, an $IC$ \emph{majority merging operator} for a profile $\underline{J_p}$ can be defined as $\Delta_{IC}(\underline{J_p})=
\min([IC],\leqslant_{\underline{J_p}})$, i.e., the set of  all models of $IC$ (denoted by [$IC$]) with minimal pseudo-distance $D^d$ to $\underline{J_p}$. The minimal pseudo-distance identifies the final collective outcome on the premises, i.e. the set of premises that support the conclusion voted by the majority of the agents and with the minimal distance among all possible models satisfying $IC$.

A  majority merging operator, often mentioned in the literature, is the operator $\Delta^{d,\Sigma}_{IC}$ defined as follows:
\vspace{-0.1cm}
\begin{enumerate}
\item $d$ is the Hamming distance --- the number of propositional letters on which two interpretations differ, i.e., $d(\omega,\omega^{\prime})=\left\vert \left\{  \pi\in \mathcal{P}|\omega (\pi)\neq\omega^{\prime}(\pi)\right\}  \right\vert$ and

\item $D^{d}(\omega,\underline{J_p})={\sum}_{i}d(\omega,J_{i,p})$ is the sum of componentwise distances $d$ defined before.
\end{enumerate}
\vspace{-0.2cm}
For example, the Hamming distance between $\omega = (1,0,0)$ and $\omega^{\prime} = (0,1,0)$ is $d(\omega, \omega^{\prime}) = 2$. In the following we use the Hamming distance because it is a well known and intuitive distance. But the Hamming distance is only one among many possible distance functions that we may use. 

The premise aggregation rule $F_{IC}$ outputs the disjunction of formulas which completely characterize the sets of judgments selected by $\Delta^{d,\Sigma}_{IC}$ as the reasons in support of the conclusion voted by the majority of the agents. Given a premise profile $\underline{J_p}$, $F_{IC}$ is  defined as:
\vspace{-0.2cm}
$$F_{IC} (\underline{J_p}) =  \bigvee \Delta^{d,\Sigma}_{IC}(\underline{J_p}) $$
\vspace{-0.05cm}
The constraint $IC$ is defined as $IC = \mathcal{R} \wedge \hat{x}$, where $\hat{x}$ is the conclusion chosen by the majority. 

The best way to illustrate our procedure is with an example. 

\begin{example}
\label{ex:doctors}
Consider a \emph{collegium medicum} that wishes to eliminate the possibility of  a patient suffering from condition X before administering a treatment. We take $v(x)=0$ if the patient is free of X.  The doctors consider the  three relevant alternative medical conditions $a$, $b$ and $c$ the patient may suffer from.
The patient is free of X if medical conditions  $a$, $b$ and $c$ are present ($v(a)=1$, $v(b)=1$ and $v(c)=1$), if all three medical conditions are absent ($v(a)=0$, $v(b)=0$ and $v(c)=0$) or if the last condition is present while the previous two are absent ($v(a)=0$, $v(b)=0$ and $v(c)=1$). In all other cases the patient is likely to suffer from X. Table \ref{tab:doctors} gives the truth table of $\mathcal{R}$.
\vspace{-0.3cm}
\begin{table}[h]
\vspace{-0.3cm}
\begin{centering}
\begin{tabular}{c||cccccccc}
   \small  $a$ &\small 0&\small 0&\small 0&\small 0&\small 1&\small 1&\small 1&\small  1\\\hline
    \small $b$ &\small 0&\small 0&\small 1&\small 1&\small 0&\small 0 &\small 1&\small 1\\\hline
    \small  $c$ &\small 0&\small 1&\small 0&\small 1&\small 0&\small 1 &\small 0&\small 1\\ \hline   
    \small $x$ &\small  0&\small 0&\small 1&\small 1&\small 1&\small 1 &\small 1 &\small 0\\
\end{tabular}
\vspace{0.2cm}
\caption{\small The truth table of $\mathcal{R}$ for the doctor example.}
\label{tab:doctors}
\end{centering}
\vspace{-1.3cm}
\end{table}
\vspace{0.2cm}

Three equally qualified members of the \emph{collegium medicum}  give their opinions shown in Table  \ref{tab:docdilemma}.  As Table \ref{tab:docdilemma} shows, the group is facing a dilemma. The majority of the conclusions from the doctors opinions indicates that the patient does not suffer from X though the majority on the premises supports the opposite conclusion.  

Our procedure (see Table \ref{tab:example1}) selects the reasons that are most compatible with the doctors' different opinions, i.e. the judgment set (1,1,1).
\vspace{-0.3cm}
\begin{table}[ht]
\begin{minipage}[b]{0.5\linewidth}\centering
\begin{tabular}{|p{1.3cm}|p{0.3cm}p{0.5cm}p{0.5cm}p{0.5cm}|p{0.3cm}p{0.5cm}|}\hline
    
 Agenda  &&\small    $a$   &\small    $b$ &  \small   $c$ & & \small   $x$ \\\hline\hline
 \small Dr. A & &\small 1         &\small 1           &\small 1         & &\small 0\\\hline 
\small Dr. B  & &\small 0         &\small 0           &\small 0         & &\small 0\\\hline
  \small Dr. C  & &\small 1         &\small 1           &\small 0        &  &\small 1\\\hline
    \small Majority & &\small 1         &\small 1           &\small 0     &     &\small 0\\\hline
\end{tabular}
\vspace{0.2cm}
\caption{\small The dilemma faced by the$\;\;\;\;\;\;$ doctors.}

\label{tab:docdilemma}

\end{minipage}
\hspace{0.2cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\begin{tabular}{|p{0.2cm}p{1.0cm}|c|c|c|c|}\hline
& &\small $J_{1,p}$  &\small $J_{2,p}$ &\small  $J_{3,p}$ &\small $\Sigma_i\; d(\omega,J_{i,p})$ \\ \hline
&\small(1,1,1)  &\small 0  &\small  3  &\small 1 &\small 4 \\ \hline
&\small(0,0,0)  &\small 3 &\small  0   &\small 2 &\small 5 \\ \hline
&\small(0,0,1)  &\small 2  &\small 1 &\small  3  &\small 6 \\ \hline
\end{tabular}
\vspace{0.2cm}
\caption{\small Selection of the  premise set from the doctors opinions under the constraint $v(x)=0$.}
\label{tab:example1}

\end{minipage}
\vspace{-1.45cm}
\end{table}

\end{example}



By applying the same procedure, the premises selected for the discursive dilemma in Table~\ref{tab:paretian} with $v(x)=0$ would be $(0,1) \vee (1,0)$, representing a tie between $X$ is good at teaching but bad at research and  $X$ is good at research but bad at teaching. 

Example \ref{ex:doctors} illustrates that, when aggregating the premises, we do not only take  into account the judgment sets of the agents that support the aggregated conclusion, but also the judgment sets of agents that do not support the conclusion. Consider for example the selection of premises  with $v(x)=~1$ in Table~\ref{tab:docdilemma}. We take also the judgment set of Dr. C into account,  although she voted for $v(x)=~1$. 

The justification for taking all individual judgments on the premises into account is two-folded. On the one hand, from the perspective of probability theory, if all judgments are independent, then more judgment sets mean a higher chance to get a better judgment. On the other hand, from the perspective of democracy, involving agents whose conclusion is not supported will give broader basis for the decision. However, we do not exclude the possibility that there are situations in which only the individuals' judgments that actually supported the aggregated conclusion should be taken into account when determining the reasons for that conclusion.



