\documentclass{llncs}
\usepackage{amssymb}
\usepackage{times}
%\usepackage{hyperref}
\usepackage{enumerate}

\newcommand{\ptop}{p2p}
\newcommand{\ptoi}{p2i}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%new version 2.0 submitted to SUM 2007 workshop
% Meltem added new material
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Aggregating Interval Orders by \\Propositional Optimization}

\author{Daniel Le Berre  \and Pierre Marquis  \and Meltem \"Ozt\"urk\thanks{ 
This work has been supported in part by  two Projects: ANR-05-BLAN-0384 and PEPS-09 37. This support is gratefully 
acknowledged by the autors. The authors also thank anonymous referees for their helpful comments and suggestions.
}}
\institute{Universit\'e Lille Nord de France, F-59000 Lille, France\\
Universit\'e d'Artois, CRIL, F-62307 Lens, France\\
CNRS, UMR 8188, F-62307 Lens, France\\
%CRIL CNRS 8188 Universit\'e d'Artois, Lens, France\\
\email{$\{$leberre, marquis, ozturk$\}$@cril.univ-artois.fr}} 
%
%
%
\newcommand{\stcons}{\mbox{$|\!\!\!\equiv$}}
\newcommand{\andd}{\mbox{$\wedge$}}
\newcommand{\orr}{\mbox{$\vee$}}
\newcommand{\sneg}{\mbox{$\neg$}}
\newcommand{\wneg}{\mbox{$\sim$}}
\newcommand{\nneg}{\mbox{$\not\sim$}}
\newcommand{\scondd}{\mbox{$\rightarrow$}}
\newcommand{\Scondd}{\mbox{$\Rightarrow$}}
\newcommand{\sconddd}{\mbox{$\rightarrow_s$}}
\newcommand{\lscondd}{\mbox{$\leftarrow$}}
\newcommand{\biscondd}{\mbox{$\leftrightarrow$}}
\newcommand{\Biscondd}{\mbox{$\Leftrightarrow$}}
\newcommand{\wcondd}{\mbox{$\rightarrow_w$}}
\begin{document}
\maketitle
\vspace{-0.3cm}
\begin{abstract}
Aggregating preferences for finding a consensus between several agents is an important 
issue in many fields, like economics, decision theory and artificial intelligence.
In this paper we focus on the problem of aggregating interval orders which are 
special preference structures allowing the introduction of tresholds for the indifference relation.
We propose to solve this problem by first translating it into a propositional optimization 
problem, namely the Binate Covering Problem, then to solve the latter using a {\sc max-sat} solver.
We discuss some properties of the proposed encoding and provide some hints about its practicability 
using preliminary experimental results. 
\end{abstract}

%\vspace{1cm}

\noindent {\bf Keywords:} Interval orders,  preference modelling and aggregation, propositional reasoning, Boolean optimization


\newcommand{\dlbcomment}[1]{{\color{red} *\footnote{\color{red}\em #1}}}
\newcommand{\mocomment}[1]{{\color{blue} *\footnote{\color{blue}\em #1}}}
%\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Aggregating preferences for finding a consensus between several
agents is an important issue in many fields, like
economics, decision theory, and artificial intelligence. Given the preferences of a set of
agents (or voters) over a set of alternatives (or candidates), where preferences
are generally formulated as binary relations such as strict preference, indifference, etc.,
preference aggregation aims at determining a collective preference
relation representing as much as possible the individual
preferences. 
%We will use the notion of ``voting rules'' %merely
%when this problem is reduced in finding a socially preferred candidate.

However many works have shown through paradoxes and impossibility 
theorems that preference aggregation is not an easy task, the famous ones are Condorcet's paradox \cite{Condorcet1785}, Arrow's theorem
\cite{arrow1book51} .%and Gibbard and Satterthwaite's theorem \cite{Gibbard73,Satterthwaite75}.
%. We cite in the following  
%some of the most famous results pointing out such difficulties 
%%Social choice theorists have shown  paradoxes and, among which the following three, which may be the most well-known
%(in all three cases we assume that there are at least 3
%alternatives): \vspace{-2mm}
%\begin{itemize}
%\item {\em Condorcet's paradox \cite{Condorcet1785}}: a
%Condorcet cycle is a sequence of candidates $x_1,\ldots, x_k$ such that
%for all $i \leq k-1$, a majority of voters prefers $x_i$
%to $x_{i+1}$, and a majority of voters prefers $x_k$ to
%$x_{1}$. Such cycles make it impossible to build a collective
%preference relation compatible with pairwise majority
%comparisons between candidates. 
%\item {\em Arrow's theorem
%\cite{arrow1book51}}: any unanimous aggregation function for which
%the pairwise comparison between two alternatives is independent of
%irrelevant alternatives
%%depends only on how the agents rank these two alternatives with respect to one another
%%, and which satisfies unanimity,
%is dictatorial;
%\item {\em Gibbard and
%Satterthwaite's theorem} \cite{Gibbard73,Satterthwaite75}: any
%surjective and nondictatorial voting rule is manipulable.
%% (that is, there exist some profiles where   some agents have an interest to report insincere preferences).
%%\end{itemize}%\vspace{-2mm}
%Some attempts to escape from such negative results have been proposed 
%so far: restricted domains, nonindependent social choice functions, etc. (see for instance \cite{Sen77,Fishburn73}).

A common approach is to consider a preference relation as a complete
preorder (i.e., a reflexive and transitive relation). In the above results each voter is supposed to present 
a complete preoder over the set of alternatives. However, such a model for preferences does not prove
adequate to all situations, and other models (generalizing the
complete preorder one) have been pointed out. In particular, different structures have been introduced for defining thresholds as in the
famous example given by Luce \cite{Luce56} about a cup of coffee.
Indeed, in contrast to the strict preference relation, the
indifference relation induced by such structures is not necessarily
transitive. Semiorders may form the simplest class of such
structures and they appear as a special case of interval orders. The
axiomatic analysis of what we call now interval orders has been
given by Wiener \cite{Wiener14}, then the term ``semiorders'' has
been introduced by Luce \cite{Luce56} and many results about their
representations are available in the literature (for more details
see \cite{Fishburn85,PirlotVincke97}). Roughly speaking, within an interval order, alternative $x_1$ is strictly preferred to alternative $x_2$ if and only if the evaluation of $x_1$ is greater than the evaluation of $x_2$ plus a threshold. It is easy to see that preorders are special cases of interval orders where the value of threshold is fixed to zero. 
%Hence it is not suprising that the three results that we presented above are also valid for interval orders.  Even if there exist many aggregation procedures proposed for preorders, there are only few ones for interval orders. 

In this paper we consider the interval order aggregation problem; to solve it, we propose a method based on the Kemeny distance which makes use of 
a translation into the Binate Covering Problem \cite{BinateCoveringProblem}. More precisely, we consider the case where the preferences of voters are interval orders and we try to find a final interval order which will be "as close as possible" to the set of voter's preferences. Let us note that having an interval order as a result of an aggregation is not a drawback for pointing out an undominated alternative since it is known that when the asymmetric part of a binary relation is transitive, which is the case of interval orders, there is always at least one such undominated alternative \cite{Sen70}. Moreover it is natural to ask an interval order as a result when preferences of voters are interval orders. Finally, as we will show it, even when the input preferences are preorders, focusing on interval orders as outputs is a way to get an aggregation which is closer to the given preferences than when preorders are targeted (just because the set of all interval orders over the!
  alternatives is 
a superset of the set of all preorders over the alternatives).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Aggregation as Optimisation}

In this paper, we consider  a finite set of alternatives $A$ on which
preference relations are applied ($|A|=n$), we represent with $a,b,c,...$ specific
elements of $A$ and $x_1, x_2, ...$ or $x,y,z, \dots$ variables ranging over the set $A$. We have a finite set of voters $V=\{v_1, \dots, v_m\}$
($|V| = m$). Voters express their preferences by the help of two binary relations represented in an explicit way
as $n^2$-matrices: the notation $a P_i b$ (resp. $a I_i b$) means that the voter $v_i$ prefers strictly alternative $a$ to $b$ (resp. is indifferent between $a$ and $b$).  $\#p(a,b)$ (resp. $\#i(a,b)$) is the number of voters $v_i$ for whom $aP_i b$ (resp. $aI_i b$) holds.  We call a {\em profile}, the set of voter's preference relations and denote it by $X=\{\langle P_1,I_1 \rangle , \langle P_2,I_2 \rangle , \dots, \langle P_m,I_m \rangle \}$; its size is in $\mathcal{O}(m.n^2)$. 

The result of the agregation is also expressed by two relations that we denote by $P$ and $I$ ($P^{-1}$ represents the inverse of $P$: $\forall x, y\in A, \ xP^{-1} y \ \mbox{iff} \ y P x$). $a P b$ (resp. $a I b$) means that alternative $a$ is preferred to alternative $b$ (resp. $a$ and $b$ are indifferent) in the resulting order. We denote it as $f(\langle P_1,I_1 \rangle , \langle P_2,I_2 \rangle , \dots, \langle P_m,I_m \rangle)= \langle P,I \rangle$.
 
 
The pair $\langle P,I \rangle$ is called a {\it preference structure} if and only if  $P$ is asymmetric, $I$ is reflexive and symmetric, $P\cup I$ is complete and $P\cap I$ is empty.  Such a pair is an interval order if and only if it is a preference structure and satisfies a property called Ferrers relation.\footnote{$\forall x,y,z,t \in A, \ xPy \wedge yIz \wedge zPt \Rightarrow xPt$.}


\begin{definition} Let $P$ and $I$ be binary relations on $A\times A$, $\langle P,I \rangle$ is an interval order if and only if 
\begin{enumerate}[i) ]
\item $P\cup I \cup P^{-1}= A\times A$ (completeness) ,
\item $P \cap I= \empty$ (exclusivity),
\item $P$ is asymmetric, $I$ is symmetric and reflexive,
\item $P. I. P \subset P$ (Ferrers relation). 
\end{enumerate}
\end{definition}

The numerical representation of interval orders is as in the following:

\begin{proposition}\cite{Fishburn85}\label{propNumRepIO}
Let $P$ and $I$ be binary relations on $A\times A$, $\langle P,I \rangle$ is an interval order if and only if there exist a mapping $g$
from $A$ to $\bbbr$ and a mapping $q$ from $\bbbr$ to
$\bbbr^+$ such that for any $x, y \in A$, we have:

\begin{tabular}{c}
$xPy \Leftrightarrow g(x) > g(y)+q(g(y)).$\\
$xIy \Leftrightarrow g(x) \leq g(y)+q(g(y)).$
\end{tabular}
\end{proposition}

%In this numerical represeSemi-orders are special cases of interval orders where the lenght of intervals unique for all alternatives.

Interval orders are quasi-orders (i.e., orders with a transitive asymmetric part). Gibbard (\cite{Gibbard69}) has showed that Arrow's theorem can be generalized to the case of quasi-orders, hence we have this impossibility result for interval orders. Pirlot and Vincke (\cite{PirlotVincke97}) have focused also on this theorem with a special attention to interval orders. Before presenting this theorem we first need the following definitions in order to state it formally:
\begin{description}
\item[weak unanimity] an aggregation procedure satisfies the weak unanimity condition if and only
 if, for all voters $v_i\in V$ and for all $a, b \in A$, $a P_i b \Longrightarrow a P b;$
\item[non-dictatorship] an aggregation procedure satisfies the non-dictatorship condition if and only if,
for no voter $v_i \in V$ such that for all possible preferences of other 
voters and for all alternatives $a$ and $b$ $a P_i b \Longrightarrow a P b;$
\item[independence of irrelevant alternatives] an aggregation procedure satisfies the independence of irrelevant alternatives
condition if and only if $\forall (\langle P_1,I_1\rangle, \dots, \langle P_m,I_m\rangle)$,  $(\langle P'_1,I'_1\rangle, \dots, \langle P'_m,I'_m\rangle)$,
$\forall a, b \in A$,

\begin{tabular}{ll}
&$(\langle P_1,I_1\rangle, \dots, \langle P_m,I_m\rangle)/ \{a,b\}=(\langle P'_1,I'_1\rangle, \dots, \langle P'_m,I'_m\rangle)/ \{a,b\}  \Longrightarrow$ \\
&$(\langle P,I \rangle),/ \{a,b\}= (\langle P',I' \rangle)/ \{a,b\}$
\end{tabular}

where $\langle P,I \rangle$ is the result on  $(\langle P_1,I_1\rangle, \dots, \langle P_m,I_m\rangle)$ , and $\langle P,I \rangle/ \{a,b\}$ is the restriction of $\langle P,I \rangle$ to $\{a, b\}$, etc.
\end{description}

\begin{theorem}[Generalized Arrow's Theorem]\cite{PirlotVincke97}\label{thmArrowIO}
If $|A|\geq 4$, if $X$ is the set of all $n$-tuples of 
%complete
interval orders on $A$ and if $Y$ is the set of all interval
orders on $A$, then there is no ($X$-$Y$)-aggregation procedure\footnote{$X$ represents here the set of voter's preferences and $Y$ the resulting order.}
satisfying simultaneously weak unanimity, non-dictatorship and
independence conditions.\end{theorem}

Note that if all the considered relations are complete preorders,
Theorem \ref{thmArrowIO} is exactly Arrow's theorem with $|A|\geq
3$. We need four alternatives for interval orders because of the definition of Ferrers relation.

There exist a number of papers addressing the aggregation issue for binary
relations as an optimization problem.
Typically, a 0/1 linear program is targeted. Contrastingly, in our approach, we
associate to each profile of binary relations an instance of {\sc bcp}, the so-called {\em Binate Covering
Problem} \cite{BinateCoveringProblem}, where the set of constraints is not any set of 0/1 linear inequations but a {\sc sat} instance.
This problem has been studied for decades by the circuit community where it is important for 
logic synthesis (minimizing the number of components needed to perform a given operation). 

From a theoretical standpoint, like 0/1 linear programming, {\sc bcp} is an {\sf
NP}-hard optimization problem (and the associated decision problem is in {\sf NP}) (see
e.g. \cite{Papadimitriou}). In practice, each clause can be translated into an equivalent 0/1 linear
inequation, but the converse does not hold.
The specific format of the constraints considered in {\sc bcp} (compared to 0/1 linear programs)
enables us to take advantage of the power of existing {\sc max-sat} solvers in order
to solve its instances in a more efficient way from the practical side.

To our knowledge there is a limited number of studies related to the aggregation of interval orders. Pirlot and Vincke \cite{PirlotVincke97} have shown that the schemes that work well for complete preorders such as lexicographic procedure or  Borda's sum of ranks do not lean themselves easily to the generalization with interval orders. They proposed two types of aggregation procedures: one consisting in aggregating numerical representations into a "global evaluation" function, and the other inspired from pairwise comparison methods. 

In this paper we propose a hybrid approach consisting in finding an interval order being optimal in the sense of minimal Kemeny distance \cite{Kemeny59} to the input profile. Intuitively, ranking the alternatives according to Kemeny's rule can be seen as the best compromise since on average it gives the "closest" social preference to the individual preferences. Our idea can be summarized as in the following: 

\begin{enumerate}
\item Determine all pairwise comparisons for which all the voters have the same opinion and build a partial order that preserves those comparisons.
\item Search within the set of feasible interval orders in order to find a closest one to the input profile.
\end{enumerate}

The first step can be easily achieved the following way:\\
\begin{tabular}{c}
$ \forall v_i \in V, \  \forall x, y \in A, \ x P_i y, \Longrightarrow x P y$, \\

$ \forall v_i\in V, \  \forall x, y \in A, \ x I_i y, \Longrightarrow x I y.$
\end{tabular}\\

The resulting $ \langle P,I \rangle$ is a partial order.

\paragraph{From partial order to interval orders}
Naturally this step provides in the majority of cases many interval orders. The worst case that we may expect is  when the partial order provided in the first step is empty. In this case we have to find all the interval orders containing $n$ objects ($n$ being the cardinality of $A$). This case gives an idea on the number of interval orders that we may have.  Stanley \cite{Stanley96} has precised the number of interval orders with $n$ elements;
%(see integer sequences CROSS REFS A000763),
for this he has made use of relations between interval orders and hyperplanes arrangement. The coefficient of the following polynomial provides the number of interval orders:
  
 \vspace{0.3cm}
 \begin{tabular}{l} 
      $z = \sum_{k\geq 0}c_k\frac{x^k}{k!}$\\  
      $z=1+x+3\frac{x^2}{2!}+19\frac{x^3}{3!}+195\frac{x^4}{4!}+2831\frac{x^5}{5!}+53703\frac{x^6}{6!}+1264467\frac{x^7}{7!}+% 35661979\frac{x^8}{8!} 
      \dots$
\end{tabular}      
 \vspace{0.3cm}
 
$z$ is the unique power series satisfying $\frac{z'}{z}=y^2, \ z(0)=1$ where $1=y(2-e^{xy}).$ The value $c_k$ of the serie $z$ is the number of interval orders on $k$ alternatives. This number grows exponentially on the number of alternatives: for instance, with just 7 alternatives we have more than one million interval orders. However, we will see in the following that we do not need to represent those interval orders explicitly. We denote by $ \langle P^{(1)}, I^{(1)}\rangle$,$\langle P^{(2)}, I^{(2)}\rangle$, $\dots $ these interval orders. 


\paragraph{Discriminating interval orders}
In our approach, the distance of an interval order $\langle P^{(i)}, I^{(i)}\rangle$ to the input profile $X$, $D(\langle P^{(i)}, I^{(i)}\rangle, X)$, will be calculated as the sum of its distance to each voter's order $\langle P_j, I_j\rangle$.\\
Let us denote this distance by  $d(\langle P^{(i)}, I^{(i)}\rangle, \langle P_j, I_j\rangle)$:

$$D(\langle P^{(i)}, I^{(i)}\rangle, X)=\sum_{ \langle P_j, I_j\rangle \in X} d(\langle P^{(i)}, I^{(i)}\rangle, \langle P_j, I_j\rangle)$$

The distance $d$ is computed using the difference between pairwise comparisons in the following way:

 $$ d(\langle P^{(i)}, I^{(i)}\rangle, \langle P_j, I_j\rangle) = \sum_{(x,y)\in A^2} \delta_{\langle P^{(i)}, I^{(i)}\rangle, \langle P_j, I_j\rangle}(x,y)$$
 
 
 $$ \delta_{(\langle P^{(i)}, I^{(i)}\rangle, \langle P_j, I_j\rangle)}(x,y) = \left\{
\begin{array}{lll}
\ptop& if & (xP^{(i)}y \ \mbox{and} \  y P_j x) \ \mbox{or} \ (yP^{(i)}x \ \mbox{and} \  x P_j y)\\
0& if & (xP^{(i)}y \ \mbox{and} \  x P_j y) \ \mbox{or} \ (xI^{(i)}y \ \mbox{and} \  x I_j y)\\
\ptoi & otherwise
\end{array}
\right.$$

Here $\ptop$ and $\ptoi$ are nonnegative constant numbers. The rationale for this definition of $d$ is to put a penalty when there is a discrepancy of preference relation between the comparison given by a voter and the one of the interval order. Naturally, a discrepancy of a strict preference (for instance $xPy$) to the inverse of this preference ($yPx$) is at least as problematic as a discrepancy of a strict preference (for instance $xPy$) to an indifference ($xIy$) for this reason we suggest that $\ptop \geq \ptoi$. Even more one can impose the strict inequality ($\ptop > \ptoi$) which will guarantee to have as a result $aIb$ when the profile with three voters is $aP_1b$, $aI_2b$ and $bP_3a$. Note that the distance used by Hudry (\cite{Hudry08}) imposes $\ptop=\ptoi=1$ and provides as a result three interval orders ($aPb, bPa$ and $aIb$) for this example.
 
We propose to represent the set of interval orders to be {\em implicitly} considered in the second step  using propositional constraints (clauses). Then, computing the interval orders closest to the profile is encoded as minimizing an objective function. Accordingly, we reduce our interval order optimization problem to the {\sc bcp} one.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Translation into the Binate Covering Problem}


We first need propositional variables $v_{xPy}$  and $v_{xIy}$ to represent all pairs of the form $xPy$ ($\forall x\neq y \in A$) and $xIy$ ($\forall x,y \in A, x \leq y$). As a consequence, $n^2 - n +\frac{n\times (n-1)}{2} + n = \frac{3\times n^2 - n}{2}$ variables must be considered. For instance, for 4 alternatives, we need 22 propositional variables. For 16 alternatives, we need 376 propositional variables.

\subsection{Implicit representation of interval orders}
\subsubsection{\label{StructuralConstraints} Structural constraints}
The following constraints express that the result of the aggregation must be an interval order. They do not depend on the voters.
\begin{itemize}
\item $P\cup I $ is complete: $\forall x < y\in A \ v_{xPy} \vee v_{xIy} \vee v_{yPx}$,

\item $P$ is asymmetric:  $\forall x < y\in A, \ \neg (v_{xPy} \wedge v_{yPx})\equiv \neg v_{xPy} \lor \neg v_{yPx}$,

\item $P$ and $I$ are exclusive:  $\forall x\not = y\in A, \ \neg (v_{xPy} \land  v_{xIy}) \equiv \neg v_{xPy} \lor \neg v_{xIy}$,

\item $I$ is symmetric by construction because a single propositional variable $v_{xIy}$ represents both $xIy$ and $yIx$.

\item $I$ is reflexive:  $\forall x\in A$,  $v_{xIx}$ is forced to be true,

\item $P\cup I$ is Ferrers:  $\forall x,y,z,t\in A,x\neq y, z\neq t,x\neq t, y \neq t, x \neq z \ (v_{xPy} \wedge v_{yIz} \wedge v_{zPt} ) \Rightarrow v_{xPt}$,
\end{itemize}

Note that we need to generate $2n(n-1)+n+n(n-1)(n-2)^2=n(n^3-5n^2+10n-5)$ structural constraints plus the unit clauses needed to preserve unanimity (see below). For 4 alternatives, it means at least 76 constraints. For 16 alternatives, it means at least 47536 constraints. The $O(n^4)$ space required by the above encoding is clearly dominated by the cost of ensuring Ferrers condition.

\subsubsection{Unanimity constraints}
Those additional constraints encode unanimity for both $P$ and $I$. They are generated according to the votes. Since they force the truth value of some variables, they simplify in practice the computation of the best interval order.  
\begin{itemize}
\item Unanimity for $P$:  $\forall x\not = y\in A, $ if $\#p(x,y)=|V|$ then   $xPy$ is forced to be true,

\item Unanimity for $I$:  $\forall x\not = y\in A, $ if $\#i(x,y)=|V|$ then   $xIy$ is forced to be true.
\end{itemize}

\subsection{Distance between interval orders and the profile}
The coefficient associated to each variable is computed according 
the individual penalty $\delta$ defined earlier and the number of voters that disagree with the interval order.
\begin{itemize}
\item $\forall x,y \in A$,  satisfying $I(x,y)$ entails that voters that strictly prefer $x$ to $y$ or $y$ to $x$ disagree with that fact, with a simple individual penalty of $\ptoi$. As a consequence, the coefficient of the variables is exactly  $\ptoi(\#p(x,y)+\#p(y,x))$,

\item $\forall x,y \in A$,  satisfying $P(x,y)$ entails that voters that are indifferent between $x$ and $y$ disagree with that fact with a simple penalty of $\ptoi$, while the voters that strictly prefer $y$ to $x$ disagree with that fact with an individual penalty of $\ptop$. So the coefficient of those variables is exactly  $\ptoi \#i(x,y)+\ptop * \#p(y,x)$.
\end{itemize}

The objective function of the binate covering problem associated with $X$ is denoted by $score_X(\langle P, I\rangle)$ and is 
$$\sum_{x \leq y \in A}\ptoi (\#p(x,y)+\#p(y,x))v_{xIy} + \sum_{x \neq y \in A} ( \ptoi \#i(x,y)+\ptop* \#p(y,x))v_{xPy}.$$

Thus the space needed to represent the objective function is in $\mathcal{O}(n^2.log_2(m))$.
Interestingly, the space needed by the encoding (constraints and objective function) is only logarithmic in the number of voters.
This renders the approach feasible for a large number of voters. On the other hand, the space needed by the encoding is in $\mathcal{O}(n^4)$;
considering that {\sc max-sat} solvers are currently able to solve {\em some} instances with millions of variables, it might be possible to solve aggregation problems up to roughly 40 alternatives (which leads to 2 millions of clauses using the above encoding). 

The result of the aggregation step is any interval order which minimizes the value of the objective function. 
An important issue is to determine whether it makes sense to use of
sophisticated {\sc sat} engine (or 0/1 linear program solver) to solve those
specific {\sc bcp} instances stemming from a translation from instances of the
aggregation problem. \cite{Hudry08} gave a positive answer to this query, by
identifying the complexity of the following decision problem:
\vspace{5mm}
\noindent {\sc score}:\\
{\bf Input:} A finite profile $X$ of binary relations $\langle P,
I\rangle$ on $A$ and a nonnegative integer $k$.\\
{\bf Question:} Does there exist an interval order $\langle P, I\rangle$
on $A$ such that
$score_X(\langle P, I\rangle) \leq k$?
\vspace{5mm}
%\begin{itemize}
%\item[{\bf Input:}] A finite profile $X$ of binary relations $\langle P,
%I\rangle$ on $A$ and a nonnegative integer $k$.
%\item[{\bf Question:}] Does there exist an interval order $\langle P, I\rangle$
%on $A$ such that
%$score_X(\langle P, I\rangle) \leq k$?
%\end{itemize}

In a nutshell Hudry showed that {\sc score} is {\sf NP}-complete as soon as the
number of voters $m$ is "sufficiently" large compared to the number $n$ of
alternatives, even in the restricted case when $X$ consists of linear orders
only, provided that $\ptop = \ptoi = 1$.
This justifies to take advantage of algorithms running in exponential time (as {\sc max-sat} solvers) in
the worst case, since polynomial time ones are hardly expected.

Hudry's {\sf NP}-hardness result extends easily to our framework
when the parameters $\ptop$ and $\ptoi$
are such that $\ptop = \ptoi $ since linear orders are interval orders; on the other
hand,
the membership to {\sf NP} of the {\sc score} probllem is obvious
in our setting: in order to determine  that an instance of this decision problem
is positive, it is enough to
guess a binary relation $\langle P, I\rangle$ on $A$  (its size is
$\mathcal{O}(n^2)$),
then to check that it is an interval order (this can be easily achieved in
polynomial
time in the size of the relation), and finally to compute in polynomial time
$score_X(\langle P, I\rangle)$ in order to compare it with $k$.

Our {\sc max-sat} algorithm for the {\sc bcp} problem is a branch-and-bound
algorithm.
During the search, each time a (partial) assignment is found that satisfies all
the constraints, the corresponding score is
computed (each unassigned variable is set to $0$) and a constraint which
eliminates all the assignments
leading to a greater bound is added, so that whenever a partial assignment leads
to a score which is worse than
this bound, a backtrack occurs. Its worst-case time complexity is simply exponential in the number of variables
under consideration
(hence linear in the size of $X$) and its space complexity is linear in the size
of the constraints (hence
quadratic in the size of $X$).
%\mocomment{
%Au secourssssssssss... Je ne comprends pas les numeros des tables.....
%}

\subsection{Examples}
As a matter of illustration, let us consider the following examples. For these examples we suppose that $\ptoi=1$ and $\ptop=2$.

\begin{example}\label{TheExample}

Consider first a case with 5 voters and 4 alternatives with the preferences of voters shown in Table \ref{TableEx1}.

\begin{table}
\begin{center}
\begin{tabular}{p{3.5cm}p{4cm}p{5cm}}
\begin{tabular}{c|c|c|c|c}
$V_1$ &$a$&$b$&$c$&$d$\\
\hline
$a$ &$I$&$P$&$P$&$P$\\
\hline
$b$ &$P^{-1}$&$I$&$I$&$P$\\
\hline
$c$ &$P^{-1}$&$I$&$I$&$P$\\
\hline
$d$ &$P^{-1}$&$P^{-1}$&$P^{-1}$&$I$\\
\end{tabular}
&
\begin{tabular}{c|c|c|c|c}
$V_2$ &$a$&$b$&$c$&$d$\\
\hline
$a$ &$I$&$P$&$I$&$P$\\
\hline
$b$ &$P^{-1}$&$I$&$P^{-1}$&$P$\\
\hline
$c$ &$I$&$P$&$I$&$P$\\
\hline
$d$ &$P^{-1}$&$P^{-1}$&$P^{-1}$&$I$\\
\end{tabular}

&

\begin{tabular}{c|c|c|c|c}
$V_3,V_4,V_5$ &$a$&$b$&$c$&$d$\\
\hline
$a$ &$I$&$P$&$P$&$P$\\
\hline
$b$ &$P^{-1}$&$I$&$I$&$P$\\
\hline
$c$ &$P^{-1}$&$I$&$I$&$P$\\
\hline
$d$ &$P^{-1}$&$P^{-1}$&$P^{-1}$&$I$\\
\end{tabular}

\end{tabular}
\end{center}
\caption{\label{TableEx1}Pairwise comparisons on 4 alternatives given by 5 voters}
\end{table}

\end{example}
\vspace{-0.3cm}
These preferences of voters can be compactly represented in a matrix where  $\forall x_i, x_j,$ $\ P(x_i,x_j)=\alpha$ means that there are $\alpha$ voters who prefer alternative $x_i$ to alternative $x_j$. Table \ref{TableEx1Matrix} represents the matrix related to the previous example. Accordingly, this matrix contains all the information needed for running our aggregation procedure. Our method find as a result the following interval order: $aPb$, $cPa$, $dPa$, $cPb$, $dPb$, $cPd$ (its distance to the profile is 12).

\begin{table}
\begin{center}
\begin{tabular}{p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}}
$P$ &$a$&$b$&$c$&$d$\\
\hline
$a$ &0&5&1&2\\
\hline
$b$ &0&0&0&2\\
\hline
$c$ &3&4&0&5\\
\hline
$d$ &3&3&0&0
\end{tabular}
\end{center}
\caption{\label{TableEx1Matrix} The number of voters agreeing for a strict preference}
\end{table}

\vspace{-0.8cm}
%Let us analyse the weighted MAX SAT procedure for this example:

%The unanimity constraint provides $aPb$ and $cPd$, if all the other pairwise comparisons are indifference, the hard constraint on Ferrers relation is violated. There are 19 interval orders containing these two preferences and being Ferrers. Among them onlyone is as close as possible to the input profile $X$ (i.e. it minimizes the value of $D(., X)$). This interval order satisfies $aPb$, $cPa$, $dPa$, $cPb$,$dPb$, $cPd$ (its distance to the profile is 12).

%\vspace{0.3cm}

\begin{example}\label{exPOIO}
Here is a second example; Table \ref{TableExPOIO} shows the pairwise comparisons given by three voters on three alternatives ($a,b,c$).
\begin{table}
\begin{center}
\begin{tabular}{ccc}
\begin{tabular}{p{0.5cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}}
$V_1$ &$a$&$b$&$c$\\
\hline
$a$ &$I$ &$P$& $I$\\
\hline
$b$ &$P^{-1}$&$I$&$P^{-1}$\\
\hline
$c$ &$I$&$P$&$I$\\
\end{tabular}

&
\begin{tabular}{p{0.5cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}}
$V_2$ &$a$&$b$&$c$\\
\hline
$a$ &$I$ &$P$& $P$\\
\hline
$b$ &$P^{-1}$&$I$&$I$\\
\hline
$c$ &$P^{-1}$ &$I$&$I$\\
\end{tabular}

&

\begin{tabular}{p{0.5cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}}
$V_3$ &$a$&$b$&$c$\\
\hline
$a$ &$I$ &$I$& $I$\\
\hline
$b$ &$I$&$I$&$I$\\
\hline
$c$ &$I$&$I$&$I$\\
\end{tabular}
\end{tabular}
\end{center}
\caption{\label{TableExPOIO} The profile of Example \ref{exPOIO}}
\end{table}

\end{example}
\vspace{-0.8cm}
The result of our aggregation procedure provides a unique interval order as close as possible to the input profile.
It is not a preorder ($a$ is preferred to $b$ and all the other comparisons are indifference), despite the fact that each preference relation
in the input profile is a preorder.
%\vspace{-0.3cm}
%\begin{table}
%\begin{center}
%\begin{tabular}{p{0.5cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}}
% &$a$&$b$&$c$\\
%\hline
%$a$ &$I$ &$P$& $I$\\
%\hline
%$b$ &$P^{-1}$&$I$&$I$\\
%\hline
%$c$ &$I$&$I$&$I$\\
%\end{tabular}
% \end{center} 
%\caption{\label{TableEx2Result}The closest interval order to the profile of Example \ref{exPOIO}}
%\end{table}

%%%%%%%%%%%%%%%%%%%%%%%
\subsection{More than one solution is often the case}

Clearly enough, there is no guarantee in general that a unique interval order
$\langle P, I\rangle$ exists,
leading to a minimal value $s^*$ for the objective function $score_X(\langle P,
I\rangle)$.
This problem is inherent to the fact that voters may have different preferences,
and it may happen in
very simple scenarios, for instance when $A$ consists of two alternatives $a$
and $b$ and $X$
consists of two interval orders $\langle P_1, I_1\rangle$ and $\langle P_2,
I_2\rangle$ on $A$
so that $a P_1 b$ and $a I_2 b$: in such a case, both $\langle P_1, I_1\rangle$
and $\langle P_2, I_2\rangle$
lead to the minimal value $s^* = \ptoi$, but not to the same sets of undominated
alternatives. Nevertheless, this plurality is problematic since decisions made using only one
of such
optimal interval orders are not necessarily robust, in the sense that the choice
of another optimal interval order could question them. Typically decisions are made by comparing alternatives or determining
undominated ones.
While robustness is a complex notion, a sufficient condition for a comparison to
be robust is when it holds
for every optimal interval order, and similarly an alternative is robustly
undominated when it is undominated
for all optimal interval orders. Formally, the following decision problems have
to be considered:
\vspace{5mm}
\noindent {\sc nec-comp($R$)}:\\
%\begin{itemize}
%\item[{\bf Input:}] A finite profile $X$ of binary relations $\langle P,
%I\rangle$ on $A$ and two alternatives
%$a$, $b$ from $A$.
%\item[{\bf Question:}] Is it the case that every interval order $\langle P,
%I\rangle$ on $A$ satisfying
%$score_X(\langle P, I\rangle) = s^*$ is such that $a R b$?
%(where $R$ = $P$ or $R = I$)?
%\end{itemize}
{\bf Input:} A finite profile $X$ of binary relations $\langle P,
I\rangle$ on $A$ and two alternatives
$a$, $b$ from $A$.\\
{\bf Question:} Is it the case that every interval order $\langle P,
I\rangle$ on $A$ satisfying
$score_X(\langle P, I\rangle) = s^*$ is such that $a R b$?
(where $R$ = $P$ or $R = I$)?\\

\noindent {\sc nec-undom}:\\
%\begin{itemize}
%\item[{\bf Input:}] A finite profile $X$ of binary relations $\langle P,
%I\rangle$ on $A$ and an alternative
%$a$ from $A$.
%\item[{\bf Question:}] Is it the case that for every interval order $\langle P,
%I\rangle$ on $A$ such that
%$score_X(\langle P, I\rangle) = s^*$, we have $a (P \cup I) b$ for every $b \in
%A$?
%\end{itemize}
{\bf Input:} A finite profile $X$ of binary relations $\langle P,
I\rangle$ on $A$ and an alternative
$a$ from $A$.\\
{\bf Question:} Is it the case that for every interval order $\langle P,
I\rangle$ on $A$ such that
$score_X(\langle P, I\rangle) = s^*$, we have $a (P \cup I) b$ for every $b \in
A$?
\vspace{5mm}

Those decision problems are "mildly" hard, since they belong to the complexity
class $\Theta_2^p$,
consisting of all decision problems which can be solved in deterministic
polynomial time
using logarithmically many calls to an {\sf NP} oracle. In order to prove the
membership of {\sc nec-comp($R$)} and {\sc nec-undom}
to $\Theta_2^p$, we consider the complementary problems and show them in
$\Theta_2^p$ as well
(this class is closed under complementation). We have already seen that {\sc
score} is in {\sf NP}.
Now, the value of $s^*$ can be computed by binary searching it within the bounds
$0$
and $m.n^2.max(p2p, p2i)$ which is a (rough) upper bound of $s^*$, and has a
value
linear in the size of $X$ since $max(p2p, p2i)$ is a constant. Hence, $s^*$ can
be computed in deterministic polynomial time
using logarithmically many calls to an {\sf NP} oracle (used to solve the {\sc
score} instances encountered
during the search, associated to the successive values of $k$) . Once this is
done, it remains to guess a binary relation
$\langle P, I\rangle$ on $A$ using a last call to the {\sf  NP} oracle, check
that it is an interval order such that
$score_X(\langle P, I\rangle) = s^*$, and finally check that $a{\bar R}b$ (resp.
that there exists a $b \in A$ such that $bPa$).
We conjecture that  {\sc nec-comp($R$)} and {\sc nec-undom} are
$\Theta_2^p$-complete.
Noticeably, when $s^*$ is part of the input, the complexity of {\sc
nec-comp($R$)} and {\sc nec-undom} falls
down to {\sf coNP}. From the practical side, when several instances of {\sc
nec-comp($R$)} or {\sc nec-undom}
sharing the same profile $X$ are to be solved, it can prove useful to compute
$s^*$ once for all during a pre-processing phase,
then to exploit it in order to solve those instances in a more efficient way.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some Theoretical Results}

We analyze here some expected properties for aggregation procedures such as 
respect of unanimity, independance, majority, etc., and
our objective is to determine whether or not our approach satisfies some of them.
We begin by the properties at work in Arrow's theorem:

\begin{description}
\item[Universality]  An aggregation procedure is universal if it accepts all configurations for the input profile. Since the input of our procedure can be any finite set of interval orders, we can conclude that our procedure is universal.

\item[Transitivity]  Arrow's theorem imposes the transitivity of the preference and the indifference relation. Our procedure provides an interval order which has a transitive preference relation $P$ but the indifference relation $I$ is not necessarily transitive. However as we mentioned in the introduction, in order to find an undominated alternative, transitivity of $P$ is enough.

\item[Weak-unanimity] Our procedure satisfies the weak unanimity condition since unanimity is imposed by our formulation as a hard constraint to be respected.

\item[Non-dictatorship] Our procedure obviously satisfies the non-dictatorship condition.
\item[Independence] Our procedure does not satisfy the condition of  independence of irrelevant alternatives: let us show it on a new example. The set of alternatives is $A=\{a,b,c,d\}$ and we have two different profiles $X$ and $X'$ which have the same votes on the subset $A'=\{c,d\}$ of $A$: 


\begin{example}\label{exIndepen}
Table \ref{exIndepen} shows the compact matrix of each profile.
\begin{table}
\begin{center}
\begin{tabular}{p{4.5cm}|p{4.5cm}}
\begin{tabular}{p{0.5cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}}
$X$ &$a$&$b$&$c$&$d$\\
\hline
$a$ & 0&0&0&1\\
\hline
$b$ &0&0&6&2\\
\hline
$c$ &4&0&0&6\\
\hline
$d$ &8&6&4&0
\end{tabular}

&
\begin{tabular}{p{0.5cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}|p{0.7cm}}
$X'$ &$a$&$b$&$c$&$d$\\
\hline
$a$ & 0&3&0&0\\
\hline
$b$ &3&0&0&3\\
\hline
$c$ &8&1&0&6\\
\hline
$d$ &2&2&4&0
\end{tabular}

\end{tabular}
\end{center}
\caption{\label{exIndepend} The compact matrix of profile $X$ and $X'$ \ref{exIndepend}}
\end{table}
\vspace{-0.3cm}
Our procedure concludes that for the profile $X$ there are two optimum solutions, in the first one $c$ is indifferent to $d$ and in the second one $d$ is preferred to $c$. However, even if the profile $X'$ has the same votes for the comparison between $c$ and $d$, our procedure concludes for $X'$ that $c$ is preferred to $d$.
\end{example}

%\item[Independence] Our procedure does not satisfy the condition of  independence of irrelevant alternatives: let us step back to Example \ref{TheExample} and add a sixth alternative $e$ with $\#p(a,e)= 4, \#p(b,e)= 3, \#p(c,e)= 2, \#p(e,c)= 1, \#p(e,d)= 3$ and all the other votes are for indifference. The new resulting preference structure has as a result $aId$ and $bId$ instead of $dPa$ and $dPb$.  Hence the comparison of $a$ and $d$ (or $b$ and $d$) depends on the position of a third alternative which is $e$.
\end{description}

We consider now some other properties that an aggregation procedure should preferably satisfy.

\begin{description}
\item[Anonymity] The result of the aggregation depends only on the preferences of voters (and for instance, not on the age, sex or seniority of candidates). Let $\mathcal{P}$ be the set of permutations of $A$, $\pi$ one element of $\mathcal{P}$. We denote by $\pi(R)$, the binary relation such as $\pi(a) \pi(R)\pi(b) \Longleftrightarrow a R b$.  An aggregation procedure is anonymous if and only if  $\forall \pi \in \mathcal{P}$,$ f(R_1,R_2, \dots, R_m)=\pi(f(\pi(R_1),\pi(R_2), \dots, \pi(R_m))).$

It is easy to see that our procedure is anonymous.

\item[Loyalty]  If there is just one voter the procedure must provide as a result the same preference as her:
$m = 1 \Longrightarrow f(R_1)=\{a \in A: a R_1 b, \forall b \in A\}.$
Again, it is easy to check that our procedure satisfies the loyalty condition
\item[Majority condition] If there is a majority of voters who prefers $a$ to $b$ then the result of the aggregation procedure must agree with this comparison:
$f$ satisfies the {\em majority condition} if and only if
$\forall (R_1, R_2, \dots, R_m) \in X, \ \forall a, b \in A$

$$ \#p(a,b)>\#p(b,a)\Longrightarrow a P b,$$
$$ \#p(a,b)=\#p(b,a)\Longrightarrow a I b.$$

Our aggregation procedure does not satisfy the majority condition as the following example shows it.
\begin{example}

Table \ref{TableExMajority} gives the number of votes for pairwise comparisons between four alternatives given by 11 voters

\begin{table}
\begin{center}
\begin{tabular}{p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}|p{0.5cm}}
$P$ &$a$&$b$&$c$&$d$\\
\hline
$a$ &0&6&5&1\\
\hline
$b$ &2&0&8&3\\
\hline
$c$ &6&2&0&1\\
\hline
$d$ &4&3&3&0
\end{tabular}
\end{center}
\caption{\label{TableExMajority} The number of voters agreeing for a strict preference}
\end{table}
\vspace{-0.8cm}

Even if the majority of voters prefer $c$ to $a$, the result of our procedure concludes that $a$ is preferred to $c$ (the output is the interval order such that $aPb$, $aPc$, $aId$, $aIa$, $bPc$, $bId$, $bIb$, $cId$, $cIc$, $dId$ and its distance to the profile is 39).
\end{example}

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}

In this paper, we have presented an optimization-based approach to interval
orders aggregation. In this approach, to every profile of interval orders, one
associates an instance of a propositional optimization problem (namely the
Binate Covering Problem); solving the latter gives in a straightforward way an
interval order (the "closest" to the input profile in some sense), which is
considered as the aggregation looked for. Among other things, we have computed
an upper bound of the size of the BCP instance associated to every profile
(showing that it is only logarithmic in the number of voters), identified some
properties satisfied (or not) by the aggregation approach.
An interesting feature of such an optimization-based approach to aggregation is
that it can be easily tuned to fit with other preference structures (e.g.
preorders, semiorders, etc.). Indeed, it is enough to point out the
corresponding hard constraints. Investigating in more depth such extensions is
a perspective for further research.

The Binate Covering Problem can be seen as a very specific case of an Integer 
Linear Program in which case efficient ILP frameworks exist (e.g. CPLEX). 
However, it looks that tools dedicated to Boolean reasoning are better suited 
to solve such problems: Weighted 
Partial MAX SAT \cite{MAXSATEvaluation} and Pseudo Boolean Optimization 
\cite{PseudoBooleanEvaluation} engines are currently receiving a lot 
of attention since international evaluations are organized regularly and many 
systems are freely available for the research community.

We designed a proof of concept tool based on the SAT4J library\cite{SAT4J}, 
a library of Boolean search engines dedicated to solving SAT, MAX SAT and 
Pseudo Boolean problems. That tool can be downloaded from \url{http://sat4j.ow2.org/}.

In order to have an idea of the applicability of our approach on a real scenario, we used the 
publicly available results of the SAT RACE 2006\footnote{\url{http://fmv.jku.at/sat-race-2006/}}. 
It is a competitive event between 16 SAT solvers on a set of 100 benchmarks. 
Here each benchmark is a voter and each solver is an alternative.
A given benchmark b prefers the SAT solver x to the SAT solver y iff x solved b 
faster than y. A given benchmark b is indifferent between the SAT solvers x and
 y iff none of x and y solved b or both of them solved b but with a roughly 
 the same CPU time (the difference is less than 1 second).
By definition, each vote is an interval order. Computing the aggregation of 
such votes means solving a binate covering problem with 376 variables and 47536 
clauses. Our aggregator takes less than one second to generate the BCP from the 
compact matrix. SAT4J takes one second to find a solution, but fails to prove 
it is optimal even after running for several hours.

We plan to test several MAXSAT and Pseudo Boolean engines on aggregation of 
real interval orders instances (including LP based ones).
%\vspace{0.5cm}
\bibliographystyle{plain}
\bibliography{biblio}

\end{document}
