\documentclass{llncs}

\usepackage{adtv1}

\title{Choquet Optimization using GAI Networks for Multiagent/Multicriteria Decision-Making}

\author{Jean-Philippe Dubus \and Christophe Gonzales \and Patrice Perny}


\institute{LIP6 - UPMC\\
104 avenue du pr\'esident Kennedy, F-75016 Paris\\
firstname.lastname@lip6.fr}

\begin{document}

\maketitle

% \begin{abstract}
% This paper is devoted to preference-based recommendation or configuration in the context of multiagent (or multicriteria) decision making. More precisely, we study the use of decomposable utility functions in the search for Choquet-optimal solutions on combinatorial domains. We consider problems where the alternatives (feasible solutions) are represented by elements of a product set of finite domains and evaluated according to different points of view (agents or criteria) leading to different objectives. Assuming that objectives take the form of GAI-utility functions over attributes, we investigate the use of GAI networks to determine efficiently an element maximizing an overall utility function defined by a Choquet integral. After recalling some basic notions linked to capacities and Choquet integrals we present two algorithms for Choquet-optimization. The first one is a multiobjective label setting algorithm allowing the implicit enumeration of Pareto-optimal solutions focusing on Choquet-optimal solutions. Then we compare this algorithm to a second one based on a ranking approach. Both algorithms have been implemented and tested on randomly drawn instances. The solutions times obtained are given for the sake of comparison.
% \end{abstract}

\begin{abstract}
This paper is devoted to preference-based recommendation or configuration in the context of multiagent (or multicriteria) decision making. More precisely, we study the use of decomposable utility functions in the search for Choquet-optimal solutions on combinatorial domains. We consider problems where the alternatives (feasible solutions) are represented as elements of a product set of finite domains and evaluated according to different points of view (agents or criteria) leading to different objectives. Assuming that objectives take the form of GAI-utility functions over attributes, we investigate the use of GAI networks to determine efficiently an element maximizing an overall utility function defined by a Choquet integral.
\end{abstract}

\noindent {\bf Keywords:} GAI-nets, Choquet Integral, Multiobjective Combinatorial Optimization, Multiagent Decision-Making, Preference-based Configuration.




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

The multiplication of preference-based configuration problems has stressed
the need for compact preference representation languages and 
for preference-based optimization 
algorithms. In this area, graphical models are omnipresent. One can
distinguish non-numerical models like CP-nets 
\cite{doms-braf02,bout-braf-doms-hoos-pool04b} and their extension to the
multiagent case mCP-nets \cite{RossiVW04} on the one hand, and numerical
models based on decomposable utility functions like UCP-nets
\cite{bout-bacc-brafXX} and GAI-nets
\cite{gonz-pern04,braz-bout05,gonz-pern-queir08} on the other hand. 
In this paper, we investigate the potential of GAI-networks to represent
and solve decision
making problems where the performance of a solution is evaluated according 
to different points of view. This type of problem occurs when several
criteria, possibly conflicting, must be considered in the decision
analysis, or when several agents are involved in the decision process. In
both cases, any feasible solution is represented by a vector of
utilities. Assuming that each of these utilities is defined by a
GAI-decomposable model, we study the use of GAI-nets to determine
efficiently a solution having a utility vector maximizing an overall
utility function defined by a Choquet integral. 

The paper is organized as follows: in Section~\ref{gai_sec} we explain how
GAI-networks are used to represent preferences in multiobjective
problems. Then, after recalling basic notions linked to capacities and
Choquet integrals (Section~\ref{choquet_sec}), we introduce a
vector-passing algorithm for Choquet-optimization (Section~\ref{algo_sec}).
Under the assumption of convex capacity, we propose a refinement of the
previous algorithm and a second algorithm based on a ranking procedure
(Section~\ref{convex_sec}). Both algorithms have been implemented and
tested on randomly drawn instances. The solutions times obtained are given
for the sake of comparison (Section~\ref{exp_sec}).  


% ===============================================================================
% ===============================================================================
\section{GAI models for individual and collective Preferences}
\label{gai_sec}

In configuration problems, alternatives (feasible solutions) are
characterized by $n$ 
variables (or attributes) $x_1, \ldots , x_n$ taking their values in finite
domains $X_1, \ldots,$ $X_n$ respectively. They can thus be seen as elements
of the product set of these domains $\XXX = X_1 \times \cdots \times
X_n$. Throughout this paper, by abuse of notation, for any set $\mathbf{Y}
\subseteq \{1,...,n\}$, $X_{\mathbf{Y}}$ refers to $\prod_{i \in \mathbf{Y}} X_i$
and $x_{\mathbf{Y}}$ to the projection of $x \in \XXX$ on
$X_{\mathbf{Y}}$. We also consider preference relations over $\XXX$ 
representable by utility functions, i.e., by functions $u : \XXX \mapsto
\IR$ such that, for all $x,y \in \XXX$, $u(x) \geq u(y)$ if and only if $x$
is preferred to $y$ or $x$ and $y$ are judged equivalent. Such functions
$u$ are used within solvers to determine the best elements in $\XXX$
\cite{keen-raif93}.

%\subsection{GAI models and GAI nets for individual preferences}

One major difficulty in using utilities lies in their elicitation:
each agent has her own preferences and, hence, her
own utility $u$ that needs be constructed prior to being used for
optimization tasks. However, on combinatorial domains such as $\XXX$, 
elicitation may be impossible as it may involve asking unreasonably large
amounts of questions to the agent. Fortunately, it is often
the case that subsets of attributes are considered independent by the
agent. For instance, the brand of a car may be irrelevant to preferences
over its colors, hence inducing an independence between color and
brand. In such cases, these independences can be exploited to drastically
reduce the elicitation burden. In the literature, different types of
independence have been studied such as {\em preferential independence} or
{\em utility independence}
\cite{kran-luce-supp-tver71,keen-raif93,bacc-grov95}, that induce different
decompositions of utility $u$ as a function of subutilities, say $u_i$'s,
defined over small sets of attributes. 

The most widely used decomposition is the additive one: $u(x) =
\sum_{i=1}^n u_i(x_i)$ for any $x = (x_1,\ldots,x_n) \in \mathcal{X}$. Note
that this model only requires eliciting and storing $u_i(x_i)$ for any
$x_i \in X_i$, $i=1,\ldots,n$.  However, such a decomposition is not always
appropriate as it inevitably rules out any interaction between attributes,
which is far from being realistic. Some generalizations of additive
utilities have thus been investigated. In particular, GAI (generalized
additive independence) decompositions introduced by~\cite{fish67} are
especially attractive as they allow quite general interactions between
attributes while preserving some decomposability. Actually, GAI
decomposition is a generalization of the additive decomposition in 
which subutilities $u_i$'s are allowed to be defined over overlapping
factors.

\begin{definition}\label{defi:gaiutil}
  Let $\mathbf{C}_{1}, \ldots,
  \mathbf{C}_{k}$ be subsets of $\mathbf{N} = \{1,\ldots,n\}$ such that
  $\mathbf{N} = \bigcup_{i=1}^{k}\mathbf{C}_{i}$. A utility function $u(\cdot)$
  over $\XXX$ is GAI-decomposable w.r.t.\ the
  $X_{\mathbf{C}_i}$'s if and only if there exist functions $u_i :
  X_{\mathbf{C}_i} \mapsto \IR$ such that:

  \vspace{1mm}

  \centerline{$ u(x_{1}, \ldots, x_{n}) = \sum_{i = 1}^{k}
    u_{i}(x_{\mathbf{C}_{i}})$,\ \ for all $x = (x_1,\ldots,x_n) \in \XXX$\ .}
\end{definition}

For instance, $u(a, b, c, d, e, f) = u_1(a, b) + u_2(c, d) + u_3(a, c,
e) + u_4(e, f)$ defined on $A \times B \times C \times D
\times E \times F$ is a GAI-decomposable utility, with
$X_{\mathbf{C}_1} = A \times B$, $X_{\mathbf{C}_2} = C \times D$,
$X_{\mathbf{C}_3} = A \times C \times E$ and $X_{\mathbf{C}_4} = E \times F$.
GAI decompositions can be represented
by graphical structures called {\em GAI networks}~\cite{gonz-pern04}:

\vspace{-1mm}

\begin{definition}\label{defi:gainet}
  Let $u(x) \!=\! \sum_{i = 1}^{k} u_{i}(x_{\mathbf{C}_{i}})$
  be a GAI utility. A GAI net repre\-senting $u$
  is an undirected graph $\GGG = (\CCC, \EEE)$ satisfying the following
  properties:

  \vspace{1mm}

  {
    \leftskip 8mm
    \parindent -0.5cm

    {\em Prop~1:} $\CCC \!=\!
    \{X_{\mathbf{C}_1},\ldots,X_{\mathbf{C}_k}\}$. 
    Vertices $X_{\mathbf{C}_{i}}$'s are called {\em cliques}. To each
    vertex $X_{\mathbf{C}_{i}}$ is associated the corresponding factor
    $u_{i}$ from the utility function $u$;

    {\em Prop.~2:} $(X_{\mathbf{C}_i},X_{\mathbf{C}_j}) \in \EEE
    \Rightarrow \mathbf{C}_i \cap \mathbf{C}_j \neq
    \emptyset$. Edges $(X_{\mathbf{C}_{i}}, X_{\mathbf{C}_{j}})$'s are labeled by
    $X_{\mathbf{S}_{ij}}$, where $\mathbf{S}_{ij} = \mathbf{C}_{i} \cap
    \mathbf{C}_{j}$. $X_{\mathbf{S}_{ij}}$ is called a {\em separator};
  
    {\em Prop.~3:} for all $X_{\mathbf{C}_i},X_{\mathbf{C}_j}$ such that
    $\mathbf{C}_i \cap \mathbf{C}_j = \mathbf{S}_{ij} \neq \emptyset$,
    there exists a path between $X_{\mathbf{C}_{i}}$ and
    $X_{\mathbf{C}_{j}}$ in $\GGG$ such that for every clique
    $X_{\mathbf{C}_{h}}$ in this path $\mathbf{S}_{ij} \subseteq
    \mathbf{C}_{h}$ (running intersection property).

  }
\end{definition}

\vspace{-0.5mm}

Cliques are drawn as ellipses and separators as rectangles. For any
GAI decomposition, by Definition~\ref{defi:gainet}, cliques 
should be the sets of variables of the subutilities. The edges in
the network represent the intersections between subsets of attributes.
Fig.~\ref{choquet_ex_fig} shows the GAI net's structure for the example given
just below Definition~\ref{defi:gaiutil}. In this paper, we shall only be
interested in GAI trees as it is not restrictive \cite{gonz-pern04}. 
For the elicitation of GAI networks, refer to 
\cite{gonz-pern04,gonz-pern05,braz-bout05}.

\begin{figure}[b]
  \def\myAB{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|}
        \hline
        u_1 & a_1 & a_2 \\
        \hline
        b_1 & (1,6,3) & (5,1,1) \\
        b_2 & (8,2,1) & (3,4,4) \\
        b_3 & (7,1,1) & (6,1,2) \\
        b_4 & (1,4,2) & (2,1,3) \\
        \hline
      \end{array}$}%
  }
  \def\myCD{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|}
        \hline
        u_2 & c_1 & c_2 \\
        \hline
        d_1 & (2,8,1) & (4,7,4) \\
        d_2 & (3,2,2) & (4,8,5) \\
        d_3 & (4,2,2) & (5,3,3) \\
        \hline
      \end{array}$}%
  }
  \def\myEF{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|}
        \hline
        u_4 & e_1 & e_2 \\
        \hline
        f_1 & (2,0,3) & (3,3,2) \\
        f_2 & (3,3,4) & (3,1,2) \\
        f_3 & (4,2,5) & (2,4,3) \\
        \hline
      \end{array}$}%
  }
  \def\myACE{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|c|c|}
        \hline
        u_3 & c_1e_1 & c_1e_2 & c_2e_1 & c_2e_2 \\
        \hline
        a_1 & (3,3,1) & (2,4,7) & (1,2,2) & (6,2,4) \\
        a_2 & (5,2,3) & (1,4,6) & (4,4,3) & (2,5,6) \\
        \hline
      \end{array}$}%
  }

  \vspace{-2.5mm}

  \centerline{\input{figures/choquet_ex.pdftex_t}}
  \caption{\label{choquet_ex_fig}Example of a GAI network with three criteria}
\end{figure}





%\subsection{Handling multiple objectives}

Consider now a finite set of objectives, criteria or agents, $M =\{1,
. . . , m\}$ and assume that any solution $x \in \XXX$ is characterized by
a utility vector $(u^1(x),\ldots,$ $u^m(x)) \in \IR^m$ where $u^i: \XXX
\rightarrow \IR$ is the $i^{th}$ utility. It measures the relative
utility of alternatives with respect to the $i^{th}$ point of view
(criterion or agent) considered in the problem. Hence, the comparison of
alternatives, say $x$ and $y$, now reduces to that of their utility vectors
$(u^1(x),\ldots,u^m(x))$ and $(u^1(y),\ldots,u^m(y))$.

Each $u^i$ is actually a single utility and, as such, can
be GAI decomposable. Assume that all $u^i$'s have the same GAI structure,
that is, the $u^i$'s are decomposable as sums of functions $u_j^i$'s
whose domains are the same for all $i$'s (but their values
differ from one $j$ to another). Then, a GAI net compactly encoding
vectors $(u^1,\ldots,u^m)$ can easily be constructed: its graphical
structure is that of the GAI net of any $u^i$
(since they are all identical), and each clique
$X_{\mathbf{C}_j}$ contains utility vectors $(u^1_j,\ldots,u^m_j)$. 
Fig.~\ref{choquet_ex_fig} shows how vectors of utilities $u^i$'s
decomposable as $u_1^i(a,b)+u_2^i(c,d)+u_3^i(a,c,e)+ u_4^i(e,f)$ can be
represented by a GAI net. In this figure, tables contain 
values of utility vectors $(u_j^1,\ldots,u_j^m)$, for fixed $j$'s.

Of course, in practice, $u^i$'s are seldom decomposable w.r.t.\ the
same GAI structure. For instance, if $\XXX$ is a set of cars, then, in a
family, the utility over $\XXX$ of the father may be decomposable as
$u^1($car$) = u_1^1($price$,$brand$) + u_2^1($power$,$speed$,$consumption$)
+ u_3^1($speed$,$security$)$ whereas that of the mother may be
$u^2($car$)= u_1^2($price$,$consumption$) + u_2^2($color$,$brand$)$, and the
utility of their son $u^3($car$) = u_1^3($brand$) + u_2^3($color$) +
u_3^3($power$,$speed$)$. In such a case, we need to find a GAI net with
``bigger'' cliques that can contain all the $u_j^i$'s functions while
encompassing as much as possible the decompositions of the $u^i$'s.
For instance, utilities $u^1$ and $u^2$ decomposable w.r.t.\ the GAI nets
on the left of Fig.~\ref{both_fig} can both be represented (less compactly)
by that of Fig.~\ref{both_fig}.c. Hence vectors $(u^1,u^2)$ are GAI
decomposable according to Fig.~\ref{both_fig}.c. This graph can be
constructed by triangulation of the union of the $u^i$'s Markov graphs
\cite{cowe-dawi-laur-spieg99,gonz-pern04}.

\begin{figure}[t]
  \centerline{\input{figures/gai8.pdftex_t}}

  \vspace{-1.9mm}

  \caption{\label{both_fig}The GAI trees representing $u^1$ and $u^2$ and
    that for $(u^1,u^2)$}

  \vspace*{-3.4mm}

\end{figure}

\vspace{-1.2mm}


% ===============================================================================
% ===============================================================================
\section{Preference Aggregation with the Choquet Integral}
\label{choquet_sec}

In a multiagent/multicriteria problem, comparing
elements of $\XXX$ amounts to comparing their respective utility
profiles. The basic preference model to compare solutions is Pareto
dominance defined, for any pair $x, y \in \XXX$ by: $x \PD y
\Leftrightarrow u^i(x) \ge u^i(y)$ for all $i \in \{1, \ldots, m\}$ and
$u^j(x) > u^j(y)$ for some  $j$.  This naturally leads
to a primary optimality concept known as Pareto-optimality. Pareto optimal
elements in a set $X \subseteq \XXX$ are those that are
Pareto-dominated by no other element in $X$, i.e., they 
have a utility profile that cannot be improved on one component
without downgrading another one. As shown in \cite{Dubusetal09}
Pareto-optimal elements in $\XXX$ can be computed using vector-valued
GAI-networks (see Fig.~\ref{choquet_ex_fig}). However, Pareto-dominance is only a
partial weak order that leaves many pairs of solutions uncompared. Hence,
the Pareto set can be huge due to the combinatorial nature of the problem,
and its exact determination requires, for some instances, prohibitive computation
times. Fortunately, decision theory provides various preference models
refining Pareto dominance and modeling various attitudes in preference
aggregation. Among them, the Choquet integral \cite{Choquet53} is one of
the most expressive decision criteria. It is an aggregation function that
generalizes weighted averages when weights are not only
attached to each component (criteria or agent) but also possibly to any
subset of components. These weights are possibly non additive and are 
represented by a {\it capacity} on $M = \{1, \ldots, m\}$. 
\begin{definition}
  A capacity on $M$ is a set function $\ca: 2^M \rightarrow [0,1]$ such that:

\vspace{0.4mm}
\centerline{$\ca(\emptyset) = 0$;\quad $\ca(M) = 1$; \quad
  $\forall A, B \in 2^M$ such that $A \subseteq B$, $\ca(A)
  \leq \ca(B)$.}
\end{definition}


\noindent For any subset $A \subseteq M$, $\ca(A)$ represents the importance of
coalition $A$. Let us first recall some definitions about capacities.

\begin{definition}
  A capacity $\ca$ is said to be {\em convex} (or
  supermodular) when $\ca(A \cup B) + \ca(A \cap B) \ge \ca(A) + \ca(B)$ for
  all $A, B \subseteq M$, and it is said to be {\em concave} (or
  submodular) when $\ca(A \cup B) + \ca(A \cap B) \le \ca(A) + \ca(B)$ for all
  $A, B \subseteq M$.
\end{definition}

\begin{definition}
  To any capacity $\ca$, we can associate a \emph{dual}
  capacity $\bar{\ca}$ defined by $\bar{\ca}(A) = 1 - \ca(M \setminus A)$
  for all $A \subseteq M$.
\end{definition}

\noindent It is well known that $\bar{\ca}$ is concave if and only if $\ca$
is convex and vice-versa. Remark that when $\ca$ is convex, we have $\ca(A)
+ \ca(M \setminus A) \le 1$, hence $\ca(A) \le \bar{\ca}(A)$. As we shall see
later, a useful concept in this case is the core of $\ca$ defined by: 

\vspace{1mm}

\centerline{$core(\ca) = \{\lambda \in \mathcal{L}: \ca(A) \le \lambda(A)
  \le \bar{\ca}(A) \}$\ ,}

\vspace{1mm}

\noindent where $\mathcal{L}$ is the set of probability distributions on
$M$ and $\lambda(A) = \sum_{i \in A} \lambda_i$ represents the probability
of $A$. The core is known
to be non-empty as soon as $\ca$ is convex \cite{Shapley71}. This
result will be used in Section 5. The Choquet integral of a utility vector
$u(x) = (u^1(x),\ldots,u^m(x))$ w.r.t.\ a capacity $\ca$ is defined by:

\vspace{1mm}

\centerline{$\displaystyle\hfill  C_{v}(u(x)) = \!\sum_{i=1}^m 
  \!\left[\ca(X^{(i)}) - \ca(X^{(i+1)}) \right]\! u^{(i)}(x) =
  \!\sum_{i=1}^m \!\left[u^{(i)}(x) - u^{(i-1)}(x) \right]\!
  \ca(X^{(i)}) \hfill (\refstepcounter{equation}\theequation)\label{CH2}$}

\vspace{1mm}

\noindent where (.) is a permutation on $\{1, \ldots, m\}$ such that $0
= u^{(0)}(x) \le u^{(1)}(x) \le \ldots \le u^{(m)}(x)$, $X^{(i)}$ $=$ $\{j \in
M$, $u^j(x) \geq u^{(i)}(x)\}$ $=$ $\{(i)$,$(i+1)$, $\ldots$, $(m)\}$ for $i
\le m$ and $X^{(m+1)} = \emptyset$. Note that $X^{(i+1)} \subset
X^{(i)}$, hence $\ca(X^{(i)}) \ge \ca(X^{(i+1)})$ for all $i$. The Choquet
integral generalizes averages with the
following interpretation based on Eq.~(\ref{CH2}): for a given
utility vector $(u^1(x), \ldots, u^m(x))$, the outcome is at least $u^{(1)}(x)$
with weight $\ca(X^{(1)}) = 1$, then it increases
from $u^{(1)}(x)$ to $u^{(2)}(x)$ with weight $\ca(X^{(2)})$, then
from $u^{(2)}(x)$ to $u^{(3)}(x)$ with weight $\ca(X^{(3)})$,
and so on... The overall integral thus results from aggregation
of marginal utility increments $[u^{(i)}(x) - u^{(i-1)}(x)]$ weighted by
$\ca(X^{(i)})$. Note that Choquet Integral includes weighted averages as particular
cases. Indeed, when $\ca$ is additively decomposable, $\ca(A) =
\sum_{i \in A} \ca_i$  for all $A \subseteq M$, where $\ca_i =
\ca(\{i\})$. Hence $\ca(X^{(i)}) - \ca(X^{(i+1)}) = \ca^{(i)}$ for all $i$
and $C_\ca(u(x)) = \sum_{i=1}^m \ca_{(i)} u^{(i)}(x) = \sum_{i=1}^m \ca_i
u^{i}(x)$. When used with a non-additive capacity, it offers enhanced 
descriptive possibilities.

\begin{table}[b]

  \vspace{-2mm}
  
  \caption{\label{capacity_table}A capacity $v$ for three criteria (named 1,2,3)}

  \vspace{-0.5mm}

  \centerline{$\scriptsize\renewcommand{\extrarowheight}{1pt}
    \begin{array}{*{9}{@{\ \ \ }c}@{\ \ \ }}
      \hline
      A & \emptyset & \{1\} & \{2\} & \{3\} & \{1,2\} & \{1,3\} & \{2,3\} &
      \{1,2,3\} \\ 
      \hline
      v(A) & 0 & 0.2 & 0.1 & 0.1 & 0.4 & 0.5 & 0.5 & 1\\
      p(A) & 0 & 0.5 & 0.4 & 0.1 & 0.9 & 0.6 & 0.5 & 1\\
      \overline{v}(A) & 0 & 0.5 & 0.5 & 0.6 & 0.9 & 0.9 & 0.8 & 1\\
      \hline
    \end{array}
    $}

\end{table}

\begin{example}\label{exChoquet}
  Consider a case with 3 criteria or agents ($M = \{1, 2, 3\}$) and 3
  solutions $x, y, z$ with utility vectors $u(x) = (15, 5, 10)$, $ u(y) =
  (10, 10, 10)$ and $ u(z) = (5, 15, 10)$ respectively, and the convex capacity
  $v$ defined in Table~\ref{capacity_table}
  (we also give its dual $\bar{v}$ and an additive capacity $p \in core(v)$).
  $C_v(u(x)) = 5 \times 1  + (10 - 5) \times 0.5 + (15 - 10) \times 0.2 =
  8.5$, $C_v(u(y)) = 10 \times 1 = 10$ and $C_v(u(z)) = 5 \times 1  + (10 -
  5) \times 0.5 + (15 - 10) \times 0.1 = 8$. Hence according to the model,
  we get: $y \succ x \succ z$. If we use the dual capacity $\bar{v}$, which
  is concave, we get $C_{\bar{v}}(u(x)) = 5 \times 1  + (10 - 5) \times 0.9
  + (15 - 10) \times 0.5 = 12$, $C_{\bar{v}}(u(y)) = 10 \times 1 = 10$ and
  $C_{\bar{v}}(u(z)) = 5 \times 1  + (10 - 5) \times 0.8 + (15 - 10) \times 0.5 =
  11.5$. Hence with $\bar{v}$ we get: $x \succ z \succ y$. Note that none
  of the two orders obtained are representable with a weighted sum because
  $x \succ y$ would imply $y \succ z$,  $y \succ x$ would imply $z \succ y$
  and conversely.  When $v$ is convex we can see that solution $y$ with a
  flat utility profile is better ranked. On the contrary, with a concave
  capacity, it seems that solutions $x$ and $z$ with contrasted profiles
  are preferred to $y$. As we shall see in Section 5, this is a general
  feature of Choquet integral: we have to use a convex capacity to exhibit
  preference for well-balanced solutions and conversely. 
\end{example}


In the next section, we investigate the determination of the optimal tuple in $\XXX$ w.r.t.\ the Choquet integral. Note that, when choosing $\ca(A) = 1$ for all non-empty $A \subseteq M$, then $C_v(u(x)) = u^{(m)}(x) = \max_{i \in M} u^i(x)$.  Hence
the determination of a Choquet-optimal solution reduces to a min-max optimization problem which is known to be NP-hard even when every function $u^i$ is an additive utility \cite{gonz-pern-queir08b}.




% ===============================================================================
% ===============================================================================
\section{A Vector-Passing Algorithm for Choquet optimization}
\label{algo_sec}

All GAI message-passing algorithms rely on
the same principle: a clique called {\em root} is chosen 
to concentrate during a {\em collect} phase all the
information relevant to compute some quantity to be optimized. This phase
is processed recursively: {\em root} asks its neighbor cliques to send it
messages containing the aforementioned relevant information; in turn, these
neighbors ask their other neighbors to send relevant information, and
so on. Once a clique has received all the information it requested, it
computes and sends the message it was asked for. Once {\em root} has
received all the information it requested, a {\em distribute} phase is
applied that propagates recursively optimal attributes instantiations from
{\em root} toward the outside of the GAI net. The result of this phase
is an optimal instantiation tuple of all the attributes of the GAI
network w.r.t.\ the quantity to be optimized.

As an illustration in the scalar case, consider a utility decomposable
according to the graph of 
Fig.~\ref{choquet_ex_fig}: $u(a,b,c,d,e,f) = u_1(a,b) + u_2(c,d) + u_3(a,c,e) +
u_4(e,f)$, where each $u_i$'s codomain is $\IR$. Assume we wish to find a tuple
maximizing $u$. Let clique $EF$ act as {\em root}. Collect
consists in $EF$ asking $ACE$ to send a message, which in turn asks both
$AB$ and $CD$ to send messages. Clique $AB$ sends message
$\phi_1(A) = \{\max_{b} u_1(a,b) : a \in A\}$ and clique $CD$ sends
$\phi_2(C)=$ $ \{\max_{d} u_2(c,d) : c \in C\}$, that is, messages
$\phi_1(A)$ and $\phi_2(C)$ contain the optimal values of $u_1$ and $u_2$
for each value of separators $A$ and $C$ respectively. Then clique
$ACE$ sends message $\phi_3(E) = \{\max_{a,c}[ u_3(a,c,e) + \phi_1(a) +
\phi_2(c)] : e \in E\}$. Finally, {\em root} $EF$ computes $\max_{e,f}
[u_4(e,f) + \phi_3(e)]$, which is the optimal value for $u$. Actually, 
as described more formally in \cite{gonz-pern-queir08}, we just
computed:

\vspace{0.7mm}

\centerline{$\displaystyle
  \max_{e,f} [ u_4(e,f) + \max_{a,c} ((\max_{b} u_1(a,b)) + (\max_c
  u_2(c,d)) + u_3(a,c,e)) ] = \max_{a,b,c,d,e,f} u \ .$}

\vspace{0.7mm}

\noindent The distribute phase just traces back the Argmax's to find the
optimal tuple.
%This algorithm is described in details in \cite{gonz-pern-queir08}.

% In a multiagent/multicriteria setting, the principle is similar.
% Assume $u$ is decomposable w.r.t.\ the GAI net of
% Fig.~\ref{choquet_ex2_fig} and that the $u_i$'s tables are those shown in
% Fig.~\ref{choquet_ex2_fig}. Note that each $u_i(\cdot)$ is a
% utility vector $(u_i^1,u_i^2,u_i^3)$. In addition, assume that criteria are
% aggregated through a weighted sum, i.e., attribute tuples $x$'s are
% evaluated through $U(x) = \sum_{j=1}^3 u^j(x)$, and we wish to find that
% tuple $x$ which maximizes $U$. Then, sums being linear, the $u_i$'s tables
% can be scalarized into tables $v_i = \sum_{j=1}^3 u_i^j$ and the
% application of the preceding paragraph on the same GAI net with tables
% $u_i$'s substituted by $v_i$'s yields optimal tuple $x$. However, as shown
% previously, a weighted sum may not be an appropriate aggregation function
% and one may resort to a non linear function such as the Choquet integral. 


In a multiagent/multicriteria setting, where the overall criterion to
optimize is a Choquet integral, there is an additional source of
complexity: the Choquet integral is not a GAI decomposable function even
when $u^i$'s are GAI decomposable. As a consequence, optimality of the 
solutions cannot be guaranteed by passing messages containing only one
locally optimal
scalar per value of separator (such as $\phi_1(a)$ above). Messages
have to carry multiple utility vectors. Indeed, assume we wish finding an
optimal tuple w.r.t.\ a Choquet integral with capacity $v$
defined by Table~\ref{capacity_table} and utility $u$ over $A \times B
\times C$ decomposable as $u_1(a,b) + u_2(b,c)$. For a given value $b$ of
$B$, assume that the message sent by clique $AB$ to $BC$ could be
$u_1(a,b) = (3,2,2)$ or $u_1(a',b) = (2,2,4)$. Both utility vectors yield
the same Choquet integral: $C_v (3,2,2) = C_v (2,2,4) = 2.2$,
hence it is tempting to send only one vector to $BC$ since both vectors
seem {\em a priori} equivalent. However, if the vector received by $BC$ is
added to $u_2(b,c) = (1,2,3)$, then $C_v (u_1(a,b)+u_2(b,c)) = 4.1 > C_v
(u_1(a',b)+u_2(b,c)) = 3.7$, and if it is added to $u_2(b,c') = (3,2,1)$,
then $C_v (u_1(a,b)+u_2(b,c')) = 3.9 < C_v(u_1(a',b)+u_2(b,c')) = 4.4$. As
a consequence, locally in clique $AB$, it is not possible to determine which
of $u_1(a,b)$ and $u_1(a',b)$ should be sent to clique $BC$ to determine
the optimal solution and we thus need to send both utility vectors on the
separator. 

%Of course, passing sets of utility vectors instead of just scalars for each
%value of the separators drastically increases the combinatorics and 
%{\em a fortiori} the response times. 
Fortunately, not all utility vectors
need be sent on separators: for any fixed value of a separator,
only Pareto-nondominated vectors need be. As Choquet
integral increases with 
each component, if $x \prefind_P y$, then $C_v(x) \geq C_v(y)$ for any
capacity $v$. Now, once the value of a separator is fixed in a GAI net, it
breaks its underlying utility into an additive 
utility. For instance, in Fig.~\ref{choquet_ex_fig}, fixing the 
value of $E$ to $e'$ decomposes $u(a,b,c,d,e',f)$ into
$w_1(a,b,c,d) + w_2(f)$ where $w_1(a,b,c,d) = u_1(a,b)
+ u_2(c,d) + u_3(a,c,e')$ and $w_2(f) = u_3(e',f)$. Hence, if
$w_1(a,b,c,d) \prefind_P w_1(a',b',c',d')$, then adding to both vectors
$w_2(f)$ results in $u(a,b,c,d,e',f)$ and $u(a',b',c',d',e',f)$
respectively, the former Pareto dominating
the latter. Hence, $C_v(u(a,b,c,d,e',f)) \geq C_v(u(a',b',c',d',e',f))$,
and tuple $(a',b',c',d',e',f)$ need not be considered as the optimal
tuple. Applying this result on utility $u$ of
Fig.~\ref{choquet_ex_fig}, if $EF$ is chosen as 
{\em root}, only nondominated utilities of message $\MMM_A$ of
Fig.~\ref{choquet_ex4_fig} need be sent from clique $AB$ to $ACE$.
Similarly, only non
dominated vectors of $\MMM_C$ need be sent from $CD$. $ACE$ now needs
only send vectors of $\MMM_E$ to clique $EF$. Thus, considering messages
containing only nondominated utility vectors, we need not examine all the
288 instantiation tuples of $\XXX$, but we just examine the 8 vectors in $u_1$ and
propagate 4 of them in $\MMM_A$; we just propagate 4 vectors out of 6 in
$\MMM_C$; clique $ACE$ combines these messages with $u_3$, thus
creating 32 new vectors, of which only 11 are transmitted to clique
$EF$. Finally, $EF$ combines $\MMM_E$ with $u_4$, thus creating 33 vectors,
and selects that which optimizes $c_v$, thus highlighting the efficient
optimization process.

\begin{figure}[b]

  \vspace{-1.5mm}

  \def\myMA{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\MMM_{A} =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        a_1 & (1,6,3) (8,2,1)\\
        a_2 & (3,4,4) (6,1,2)\\
        \hline
      \end{array}$}%
  }
  \def\myMC{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\MMM_{C} =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        c_1 & (2,8,2) (4,2,2)\\
        c_2 & (4,8,5) (5,3,3)\\
        \hline
      \end{array}$}%
  }
  \def\myME{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\MMM_{E} =\,
      \begin{array}{@{}|@{\ }c@{\ }l@{\ }|@{}}
        \hline
        e_1: & (6,17,5) (11,16,12) (14,13,10) (15,8,8)\\
        e_2: & (5,18,11) (11,16,12) (18,12,10) (19,7,8) \\
        & (9,17,15) (12,14,13) (13,9,11) \\
        \hline
      \end{array}$}%
  }
  \centerline{\input{figures/choquet_ex4.pdftex_t}}
  \caption{\label{choquet_ex4_fig}Sending nondominated messages toward 
    {\em root} $EF$}
\end{figure}

%The Pareto pruning described above is local in the sense that it uses only
%informations local to the clique sending its message, i.e., the
%combination of its utility table and the messages it received. 
An additional (global) pruning can be used in conjunction with the above
local pruning to speed-up the search: assume that,
during our search, we exhibited a complete instantiation $x$ having
utility vector $u(x)$. For a new instantiation $y$ to be
optimal, $u(y)$ must not be Pareto dominated by $u(x)$. 
As in the preceding paragraph, assume that the value of separator $E$ is
fixed to $e'$, hence decomposing $u$ into $w_1 + w_2$ as described
above and assume that we know for sure that, for any $f \in F$,
$u_3(e',f) \notprefind_P h$ for a given vector $h$. Then, if $u(x) \prefind_P
w_1(a,b,c,d) + h$, no instantiation $f$ is such that $w_1(a,b,c,d) + w_2(f)
\succ_P u(x)$ and, thus, $w_1(a,b,c,d)$  needs not be sent on separator
$E$. In this paper, we considered the following heuristic $h$: given
a set of vectors $Z = \{(z_i^1,\ldots,z_i^m), i \in \{1,\ldots,r\}\}$, $h$
is defined as $h = \mymax{Z} = (z^1,\ldots,z^m)$ where $z^j = \max
\{z_1^j,\ldots,z_r^j\}$ for all $j \in \{1,\ldots,m\}$. For clique $AB$ of
Fig.~\ref{choquet_ex_fig}, $h(a) = \mymax{\{u_3(a,c,e) + u_2(c,d) +
  u_4(e,f)\}}$ for all $a \in A$. However, to speed up $h$'s computation,
we approximate it by $h'(a) = \mymax{\{u_3(a',c,e) + \mymax{\{u_2(c',d) :
    c'=c\}} + \mymax{\{u_4(e',f) : e'=e\}} : a'=a\}}$
as follows: first compute $\HHH_E^D = \mymax{\{u_4(e,f)\}}$ for all $e \in E$,
then $\HHH_C^C = \mymax{\{u_3(c,d)\}}$ for all $c \in C$. Finally,
compute $u_3 + \HHH_C^C + \HHH_E^D$ and apply operator $\mymaxM$ on it,
resulting in $\HHH_A^D$ (see Fig.~\ref{choquet_ex2_fig}).
The same applies to clique $CD$: $h'(c) = \mymax{\{u_3(a,c',e) +
  \mymax{\{u_1(a',b) : a'=a\}} + \mymax{\{u_4(e',f) : e'=e\}} :
  c'=c\}}$. Here again, there just needs to compute $\HHH_A^C =
\mymax{\{u_1(a',b) : a'=a\}}$, then $u_3 + \HHH_A^C + \HHH_E^D$ and apply
operator $\mymaxM$. 

To avoid redundant computations, we can use the
following message-passing scheme: let $EF$ act as root. Collect: $EF$
asks $ACE$ to send a message, which in turn asks 
$AB$ and $CD$ to send messages. $AC$ sends message 
$\HHH_A^C = \{\mymax{\{u_1(a',b) : a'=a\}} : a \in A\}$. Similarly, clique
$CD$ sends message $\HHH_C^C = \{\mymax{\{u_3(c',d) : c'=c\}} : c \in C\}$.
Finally, $ACE$ sends on separator $E$ message 
$\mymax{\{u_3+\HHH_A^C + \HHH_C^C\}}$ for each value $e \in E$ (see
Fig.~\ref{choquet_ex2_fig}.a). Distribute phase: $EF$ sends on $E$ message
$\HHH_E^D = \{\mymax{\{u_4(e',f) : e'=e\}} : e \in E\}$. Clique $ACE$ now
computes $\mymax{\{u_3 + \HHH_A^C + \HHH_E^D\}}$ and sends it to $CD$, and 
$\mymax{\{u_3 + \HHH_C^C + \HHH_E^D\}}$ and send it to $AB$. In other
words, before sending a message to a neighbor, a clique combines the
messages it received from all its other neighbors and, then, applies
operator $\mymaxM$. At the end of the distribute phase, each message
$\HHH^D$ corresponds to heuristic $h'$ 
(Fig.~\ref{choquet_ex2_fig}.b).

\begin{figure}[b]
  \def\myHAC{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\HHH_{A}^C =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        a_1 & (8,6,3) \\
        a_2 & (6,4,4) \\
        \hline
      \end{array}$}%
  }
  \def\myHAD{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\HHH_{A}^D =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        a_1 & (14,16,12) \\
        a_2 & (13,17,14) \\
        \hline
      \end{array}$}%
  }
  \def\myHCC{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\HHH_{C}^C =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        c_1 & (4,8,2) \\
        c_2 & (5,8,5) \\
        \hline
      \end{array}$}%
  }
  \def\myHCD{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\HHH_{C}^D =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        c_1 & (15,14,13) \\
        c_2 & (17,13,13) \\
        \hline
      \end{array}$}%
  }
  \def\myHEC{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\HHH_{E}^C =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        e_1 & (15,17,12) \\
        e_2 & (19,18,15) \\
        \hline
      \end{array}$}%
  }
  \def\myHED{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\HHH_{E}^D =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        e_1 & (4,3,5) \\
        e_2 & (3,4,3) \\
        \hline
      \end{array}$}%
  }
  \centerline{\input{figures/choquet_ex2.pdftex_t}}
  \caption{\label{choquet_ex2_fig}Propagation of heuristics information}
\end{figure}

We can now propose an algorithm in the spirit of
MOA$^*$ \cite{StewW91} pruning dominated utility vectors, thus
reducing the number of vectors sent on separators. First, using $h'$
and a collect, we propagate toward {\em root} (here $EF$)
on each sepa\-rator the most promising utility vectors, i.e., those that,
given $h'$, have the highest Choquet integrals:
clique $AB$ thus sends toward $ACE$ message $\MMM_A$ containing, for
each $a \in A$, the vector $u_1(a,b)$ maximizing
$C_v(w_1(a,b))$, where $w_1(a,b)= $ $u_1(a,b) + \HHH_A^D(a)$. 
Fig.~\ref{choquet_ex3_fig} shows the values of vectors $w_1$'s. In addition,
vectors $u_1$'s that are not inserted into $\MMM_A$ and that are not Pareto
dominated by other $u_1$'s are stored into a set of ``open vectors''
denoted by $\LLL$ (see Table~\ref{choquet2_table}). Set $\LLL$ thus
corresponds to {\em a priori} less promising vectors that may yet be
optimal and, as such, that will need to be sent later on on separators to
guarantee the correctness of the algorithm. 
Similarly, clique $CD$ sends message $\MMM_C$ containing the $u_2$'s
maximizing, for each $c \in C$, $C_v(w_2(c,d))$ where 
$w_2(c,d) = u_2(c,d) + \HHH_C^D(c)$. In
addition, non dominated $u_2$'s not belonging to
$\MMM_C$ are added to $\LLL$. Clique $ACE$ now computes vectors $u_3' = u_3 +
\MMM_A + \MMM_C$, which correspond to utility of instantiations of
attributes $A,B,C,D,E$. Clique $ACE$ sends in $\MMM_E$ those $u_3'$'s that
maximize, for each value of separator $E$, $C_v(w_3)$, where $w_3(a,c,e) =
u_3'(a,c,e) + \HHH_E^D(e)$, i.e., the most promising (so far) utility
vectors. The other $u_3'$ vectors are stored into $\LLL$. Now $EF$ can
compute vectors $u_4'(e,f) = u_4(e,f) + 
\MMM_E(e)$, which correspond to utilities of complete tuples, and
select that which maximizes $C_v$. Let us call $u^*$ this utility
vector. By Fig.~\ref{choquet_ex3_fig}, $u^* = (15,18,17)$ and $C_v(u^*) =
16.1$.

\begin{figure}[t]
  \def\myAB{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|}
        \hline
        w_1 & a_1 & a_2 \\
        \hline
        b_1 & (15,22,15) & (18,18,15) \\
        b_2 & (22,18,13) & (16,21,18) \\
        b_3 & (21,17,13) & (19,18,16) \\
        b_4 & (15,20,14) & (15,18,17) \\
        \hline
      \end{array}$}%
  }
  \def\myCD{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|}
        \hline
        w_2 & c_1 & c_2 \\
        \hline
        d_1 & (17,22,14) & (21,20,17) \\
        d_2 & (18,16,15) & (21,21,18) \\
        d_3 & (19,16,15) & (22,16,16) \\
        \hline
      \end{array}$}%
  }
  \def\myEF{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|}
        \hline
        u_4' & e_1 & e_2 \\
        \hline
        f_1 & (13,16,15) & (21,15,12) \\
        f_2 & (14,19,16) & (21,13,12) \\
        f_3 & (15,18,17) & (20,16,13) \\
        \hline
      \end{array}$}%
  }
  \def\myACE{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{|c|c|c|c|c|}
        \hline
        w_3 & c_1e_1 & c_1e_2 & c_2e_1 & c_2e_2 \\
        \hline
        a_1 & (19,10,9) & (17,12,17) & (17,15,13) & (21,16,13) \\
        a_2 & (16,11,14) & (11,14,15) & (15,19,17) & (12,21,18) \\
        \hline
      \end{array}$}%
  }
  \def\myMA{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\MMM_{A} =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        a_1b_2 & (8,2,1) \\
        a_2b_2 & (3,4,4) \\
        \hline
      \end{array}$}%
  }
  \def\myMC{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\begin{array}{c}
        \MMM_{C} =\\
        \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
          \hline
          c_1d_3 & (4,2,2) \\
          c_2d_2 & (4,8,5) \\
          \hline
        \end{array}
      \end{array}$}%
  }
  \def\myME{{\scriptsize\renewcommand{\extrarowheight}{1pt}%
      $\MMM_{E} =\,
      \begin{array}{@{}|@{\ }c@{:\ }c@{\ }|@{}}
        \hline
        a_2c_2e_1 & (11,16,12) \\
        a_1c_2e_2 & (18,12,10) \\
        \hline
      \end{array}$}%
  }
  \centerline{\input{figures/choquet_ex3.pdftex_t}}
  \caption{\label{choquet_ex3_fig}The vector message-passing algorithm}

  \vspace{-2.8mm}

\end{figure}

\begin{table}[b]

  \vspace{-2.7mm}

  \caption{\label{choquet2_table}The set of open vectors $\LLL$}


  \vspace{-0.2mm}

  \centerline{$
    \begin{array}{ccc@{\quad\quad}ccc@{\quad\quad}ccc}
      \hline
      \mbox{tuple} & u_i,u_i' & C_v(w_i) &
      \mbox{tuple} & u_i,u_i' & C_v(w_i) &
      \mbox{tuple} & u_i,u_i' & C_v(w_i) \\
      \hline
      a_1b_1 & (1,6,3) & 15.7 &
      a_2b_3 & (6,1,2) & 17.2 &
      c_1d_1 & (2,8,1) & 16.0 \\
      c_2d_3 & (5,3,3) & 17.2 &
      a_1c_1e_1 & (15,7,4)  & 11.3 &
      a_1c_2e_1 & (13,12,8) & 14.4 \\
      a_2c_1e_1 & (12,8,9)  & 12.9 &
      a_1c_1e_2 & (14,8,10) & 13.3 &
      a_2c_2e_2 & (9,17,15) & 15.3 \\
      \hline
    \end{array}
    $}
\end{table}

To ensure correctness, we need to send messages of $\LLL$
toward {\em root} and check whether they yield better $C_v$'s. But
before, we can prune from $\LLL$ all vectors $u_i$'s such that
$C_v(w_i) \leq C_v(u^*)$, since $w_i = u_i + h'$ is an
upper bound on the utility of complete tuples compatible with
$u_i$. The set $\LLL$ of
Table~\ref{choquet2_table} thus reduces to the utility vectors of
instantiations $a_2b_3$ and $c_2d_3$. Note the efficiency of this
pruning rule. We now add the most
promising vector of $\LLL$ to its appropriate separator (here, we can 
add $u_1(a_2,b_3)$ to $\MMM_A$) and remove it from $\LLL$, then clique
$ACE$ updates its $u_3'$ table by computing all the new combinations
$u_3'(a_2,c,e) = u_3(a_2,c,e) + u_1(a_2,b_3) + \MMM_C(c)$. These new
combinations are added $\LLL$, 
provided that their $C_v(w_3) > C_v(u^*)$ and that they are not Pareto
dominated by other $u_3'$'s (for fixed values of separator $E$). The same
process is applied until $\LLL$ is empty. When a vector from $\LLL$ is
added to the separator adjacent to {\em root}, the latter updates the value
of $u^*$ and prunes $\LLL$. When $\LLL$ is empty, all
possible optimal combinations have been tested and $u^*$ is an optimal utility
vector.

This process is formalized in function {\tt Choquet} below. In this
function, we do
not use $u_i$'s but rather labels, i.e., triples
$\mylabel{v}{X_{\mathbf{C}_i}}{x_{\mathbf{D}}}$, where $v$ is a utility
vector, $X_{\mathbf{C}_i}$ denotes the clique that created the label and
$x_{\mathbf{D}}$ is the partial instantiation yielding
$v$. For a given clique $X_{\mathbf{C}_i}$, $\dolabel{u_i}$
is table $u_i$ in which all vectors are substituted by their
label. For a given set of labels $\MMM$,
$\MMM[x_{\mathbf{E}}]$ denotes the subset of labels
$\mylabel{v}{X_{\mathbf{C}_i}}{y_{\mathbf{D}}} \in \MMM$ such that
$x_{\mathbf{D \cap E}} = y_{\mathbf{D \cap E}}$, and 
$\MMM \oplus \NNN =$ $\{\mylabel{v+w}{X_{\mathbf{E}}}
{x_{\mathbf{C} \cup \mathbf{D}}} :
\mylabel{v}{X_{\mathbf{C}_i}}{x_{\mathbf{C}}} \in \MMM$ and
$\mylabel{w}{X_{\mathbf{C}_j}}{x_{\mathbf{D}}} \in  \NNN\}$. Finally, for 
any $X_{\mathbf{C}_i}$, we denote
$X_{\mathbf{C}_{p(i)}}$ the clique adjacent to $X_{\mathbf{C}_i}$ on the
path between {\tt root} and $X_{\mathbf{C}_i}$, and we denote 
$\adj{i}$ the set of cliques adjacent to $X_{\mathbf{C}_i}$ except
$X_{\mathbf{C}_{p(i)}}$.

\vspace{1mm}

\begin{function}{Choquet}{}
  01 & set of open labels $\LLL \leftarrow \emptyset$; \ \ let {\tt root}
  be any clique\\ 
  02 & \keyw{for all} cliques $X_{\mathbf{C}_i}$ from the leaves to the
  {\tt root} \keyw{do} \\
  03 & \tab$\UUU \leftarrow \dolabel{u_i} \oplus_{X_{\mathbf{C}_k} \in
    \adj{i}} \MMM_k$\\ 
  04 & \tab $\MMM_i\leftarrow\{\ \UUU$'s most promising label for each
  value of separator $X_{\mathbf{S}_{ip(i)}}\}$\\
  05 & \tab$\LLL \leftarrow \LLL \cup 
  \{\myNDP{\UUU[x_{\mathbf{S}_{ip(i)}}] \backslash
    \MMM_i[x_{\mathbf{S}_{ip(i)}}]} \mbox{ for all } 
  x_{\mathbf{S}_{ip(i)}} \in X_{\mathbf{S}_{ip(i)}}\}$\\
  06 & \tab send message $\MMM_i$ on separator $X_{\mathbf{S}_{ip(i)}}$\\
  07 & \keyw{done}\\
  08 & $C_v^{best} \leftarrow \max_{L \in \MMM_{\mbox{\scriptsize\tt root}}} C_v(L)$ \\
  09 & \keyw{while} $\LLL \neq \emptyset$ do\\
  10 & \tab let $L = \mylabel{v}{X_{\mathbf{C}_i}}{x_{\mathbf{D}}}$ be the
  most promising label in $\LLL$;\ \ remove $L$ from $\LLL$\\
  11 & \tab $\MMM_{i} \leftarrow \MMM_{i} \cup \{L\}$; \ \ 
  $\UUU'_{p(i)} \leftarrow \{L\} \oplus \dolabel{u_{p(i)}}
  \oplus_{X_{\mathbf{C}_k} \in \adj{p(i)} \backslash \{X_{\mathbf{C}_i}\}} \MMM_k$\\ 
  12 & \tab\keyw{if} $p(i) =$ {\tt root} \keyw{then} \\
  13 & \tab\tab$C_v^{best} \leftarrow \max\{C_v^{best}, \max_{L \in
    \UUU'_{p(i)}} C_v(L)\}$\\ 
  14 & \tab\tab remove from $\LLL$ labels $L$'s such that 
  $C_v(L \oplus \HHH_{X_{\mathbf{C}_i}}^{\DDD}) \leq C_v^{best}$\\
  15 & \tab\keyw{else} \\
  16 & \tab\tab $\FFF \!\leftarrow\! \{L \in \LLL$ whose clique
  is $X_{\mathbf{C}_{p(i)}}\}$; $\LLL \leftarrow 
  (\LLL \backslash \FFF) \cup \myNDP{\FFF \cup \UUU'_{p(i)}}$\\
  17 & \keyw{done}\\
  18 & \keyw{return} $C_v^{best}$
\end{function}

\vspace{-0.4mm}

% ===============================================================================
% ===============================================================================
\section{The case of convex capacities}
\label{convex_sec}

Convex capacities are of special interest for Choquet integrals due to their
interpretation in terms of preference aggregation: they convey an idea of
compromise or fairness named hereafter {\em preference 
  for well balanced solutions}, meaning intuitively that smoothing or
averaging a cost vector improves the alternative. A useful
formalization of this idea has been introduced in \cite{ChateauTallon02}
through an axiom named {\em ``preference for diversification''} due to its
interpretation in the context of portfolio management. This axiom can be
reformulated in our framework as: 

\begin{definition}[Preference for well-balanced solutions]
Preference for well-balanced solutions holds for a relation $\succsim$ on
$\XXX$ if, for any $n$ utility vectors $u_1,$ $\ldots,$ $u_n \in \IR$, and
for all real numbers $\alpha_1, \ldots, \alpha_n \ge 0$ such that
$\sum_{i=1}^n \alpha_i = 1$:

\vspace{1mm}

\centerline{$[u_1 \sim u_2 \sim \ldots \sim u_n] \Longrightarrow 
  \sum_{i=1}^n \alpha_i u_i \succsim u_k, ~~k = 1, \ldots, n\ .$}
\end{definition}
When using a Choquet Integral, the above axiom 
is equivalent to choosing a convex capacity $\ca$ as shown in
\cite{ChateauTallon02}. Coming back to Example~\ref{exChoquet}, we can
imagine a fourth solution $w$ with utility vectors $u(w) = (12.5, 5, 10)$
such that $C_v(u(w)) =  5 \times 1  + (10 - 5) \times 0.5 + (12.5 - 10)
\times 0.2 = 8$. Now, remarking that $C_v(u(z)) = C_v(u(w)) = 8$, preference
for well-balanced solutions induced by the convexity of $v$ implies that
vector $0.5 u(z) + 0.5 u(w) = (9.75, 10, 10)$ would be preferred to
$u(z)$ and $u(w)$. Observing that $u(y)$ Pareto-dominates $u(w)$,
we deduce that $u(y)$ is also preferred to $u(z)$ and $u(w)$ by
monotonicity of the Choquet integral. Hence resorting to a convex capacity
might be natural in many decision situations where a compromise is sought
among conflicting points of view. Let us show now how the convexity of $v$
can be exploited on the algorithmic side. 

Let $C_v(u(x))$ be the value of the Choquet integral for any
$x$, and let $\bar{u} : \XXX \mapsto \IR$ be a convex combination
of marginal utilities defined by: 
$\bar{u}(x) = \sum_{i = 1}^m p_i u^i(x)$ where $p$ is a probability
distribution in $core(v)$. Such a distribution can be
determined using a greedy algorithm \cite{jaff95} (such a $p$
is given in Table~\ref{capacity_table}). Then the following property holds:
$\bar{u}(x) \geq C_v(u(x))$ for all $x \in \XXX$ 
\cite{GalandPerny07,Queiroz08}.  Hence $\bar{u}(x)$ 
is an upper bound for the Choquet integral. This can be
exploited in the algorithm of Section~\ref{algo_sec} in conjunction with
the pruning rule of heuristic $h'$: after scalarizing the tables of utility
vectors of Fig.~\ref{choquet_ex_fig} by $\bar{u}_i(x) = \sum_{j = 1}^m p_j
u^j_i(x)$, applying the same process that enabled us to compute $\HHH^D$ with
these new tables yields a scalar heuristic $\HHH^p$ stored on each separator.
$\HHH^p$ can be used to prune any utility vector $u_j'$ to be sent by
clique $X_{\mathbf{C}_j}$ on a separator whenever 
$\bar{u}_j + \HHH_j^p \leq C_v(u^*)$.

Utility $\bar{u}$ can also be used directly for
computing a Choquet-optimal element. As a linear
combination of GAI utilities, $\bar{u}$ is also a GAI function. Hence, we 
can rank efficiently elements of $\XXX$ by decreasing value of $\bar{u}(x)$
\cite{gonz-pern-queir08b}. 
Now, assume that $x^{1}, ..., x^{k}$, the $k$-best elements on $\XXX$
w.r.t. $\bar{u}$, have been computed. Let $\hat{x}^{k} =
\mbox{argmax}_{i = 1,\ldots,k} C_v(u(x^{i}))$. If $C_v(u(\hat{x}^{k})) \geq
\bar{u}(x^{k})$, then $\hat{x}^{k}$ is the optimal choice for $C_v$. Indeed,
as we rank elements w.r.t.\ $\bar{u}$, for any $k' > k$, $\bar{u}(x^{k'}) \leq
\bar{u}(x^{k})$, and since $\bar{u}(x) \geq C_v(u(x))$ for all $x \in \XXX$,
$C_v(u(x^{k'})) \leq \bar{u}(x^{k'}) \leq \bar{u}(x^{k}) \leq
C_v(u(\hat{x}^{k}))$. Consequently, the optimal choice for $C_v$ can be
obtained by ranking elements $x^{i}$ w.r.t.\ $\bar{u}$ until the maximum value of
the $C_v(u(x^{j}))$'s for all the $x^{j}$'s found so far, exceeds 
$\bar{u}(x^{i})$. This is another way of generating $C_v$ optimal
elements in $\XXX$ but, contrary to algorithm
presented in Section~\ref{algo_sec}, this algorithm is only feasible for a
capacity with a non-empty core. This is obviously the case when $v$ is
convex. 


% ===============================================================================
% ===============================================================================
\section{Experimentations}
\label{exp_sec}


In order to evaluate in practice the performance of our algorithms, we
compared the vector-passing algorithm of Section~\ref{algo_sec} (hereafter
denoted VPA$^*$), VPA$^*$ with heuristic $\HHH^P$ (denoted VPA$^*+$S) and
the ranking algorithm mentioned above (Rank). In
each experimentation, $X_i$'s domains were all of size 5. GAI networks were
randomly generated with an average of 3.5 attributes per clique. Utility
tables were filled with numbers drawn randomly between 0 and 100. All
experiments were performed on a 2.13GHz PC with 3GB of RAM. The tables
below report average response times in seconds over 2000 experiments. 
For Table~\ref{expe_table}.a, we generated
random capacities (not necessarily convex). VPA$^*$ reveals efficient for
instances where the ranking approach does not apply (non-convex cases).
Tables~\ref{expe_table}.b and \ref{expe_table}.c are given for the sake of
comparison of the two variants of VPA$^*$ with Rank in the convex
case. Rank is known to be very efficient when criteria are positively
correlated. We deliberately generated instances with conflicting (negatively
correlated) criteria to check whether VPA$^*$ was able to outperform Rank in
this case. The answer is clearly positive considering
Tables~\ref{expe_table}.b and \ref{expe_table}.c.

\begin{table}[t]
  
  \caption{\label{expe_table}Response times for Choquet optimization}

  \vspace{-1mm}

  \centerline{\fontsize{8pt}{8pt}\selectfont\renewcommand{\extrarowheight}{1pt}
    \begin{tabular}{c@{\quad}c@{\quad}c}
      \begin{tabular}{c@{\quad}c@{\quad}c}
        \hline
        & $m=2$ & $m=5$ \\
        $n$ & VPA$^*$  & VPA$^*$ \\
        \hline      
        5  & 0.004 & 0.015    \\
        10 & 0.06  & 34.27    \\
        15 & 13.62  & 467.35  \\
        \hline
      \end{tabular} &
      \begin{tabular}{c@{\quad}c@{\quad}c@{\quad}c}
        \hline
        \multicolumn{4}{c}{$m=2$, $v$ convex} \\
        $n$ & VPA$^*$ & VPA$^*+$S & Rank \\
        \hline
        5  &  0.004 & 0.003 & 0.007 \\
        10 &  0.06  & 0.05  & 0.47  \\
        15 &  11.30 & 6.55  &  $>$1200 \\
        \hline
      \end{tabular} &
      \begin{tabular}{c@{\quad}c@{\quad}c@{\quad}c}
        \hline
        \multicolumn{4}{c}{$m=5$, $v$ convex} \\
        $n$ & VPA$^*$ & VPA$^*+$S & Rank \\
        \hline
        5  &  0.012  & 0.008  & 0.009  \\
        10 &  33.34  & 0.28   & 9.62   \\
        15 &  451.84 & 443.76 &  $>$1200   \\
        \hline
      \end{tabular}\\
      Table~\ref{expe_table}.a & Table~\ref{expe_table}.b & Table~\ref{expe_table}.c
    \end{tabular}}

  \vspace{-3mm}

\end{table}


%\show\thebibliography

% \begin{table}[h]

%  \vspace{-1mm}

%  \caption{\label{expe_table}Response times for Choquet optimization}
 
% \centerline{\fontsize{8pt}{8pt}\selectfont\renewcommand{\extrarowheight}{1pt}
%    \begin{tabular}{c@{\quad}c@{\quad}c}
%      \begin{tabular}{c@{\quad}c@{\quad}c}
%        \hline
%        & $m=2$ & $m=5$ \\
%        $n$ & VPA$^*$  & VPA$^*$ \\
%        \hline            5  & 0.001 & 0.005    \\
%        10 & 0.018 & 0.585    \\
%        15 & 0.601 & 2177.58  \\
%        \hline
%      \end{tabular} &
%      \begin{tabular}{c@{\quad}c@{\quad}c@{\quad}c}
%        \hline
%        \multicolumn{4}{c}{$m=2$, $v$ convex} \\
%        $n$ & VPA$^*$ & VPA$^*+$S & Rank \\
%        \hline
%        5  & 0.002  & 0.001  & 0.004    \\
%        10 & 0.074  & 0.029  & 1.006    \\
%        15 & 11.329 & 10.311 & $>$ 3600 \\
%        \hline
%      \end{tabular} &
%      \begin{tabular}{c@{\quad}c@{\quad}c@{\quad}c}
%        \hline
%        \multicolumn{4}{c}{$m=5$, $v$ convex} \\
%        $n$ & VPA$^*$ & VPA$^*+$S & Rank \\
%        \hline
%        5  & 0.003    & 0.002   & 0.007     \\
%        10 & 63.687   & 37.639  & 8.854     \\
%        15 & $>$ 3600 & 2328.86 &  $>$ 3600 \\
%        \hline
%      \end{tabular}\\
%      Table~\ref{expe_table}.a & Table~\ref{expe_table}.b & Table~\ref{expe_table}.c
%    \end{tabular}}
% \end{table} 

%\section{conclusion}


\bibliography{adtv1}
\bibliographystyle{splncs}
%\bibliographystyle{alpha}


\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

