%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\documentclass{sig-alternate}

%\documentclass{article}
%%\documentclass[letterpaper]{aamas2008}
%\usepackage{amssymb}
%\usepackage{latexsym}
%%\usepackage{color}

%\documentclass{article}
%\documentclass[authoryear,lp,12pt]{elsarticle}

\documentclass{llncs}

%\documentclass[letterpaper]{article}
%\usepackage{aaai}
%\documentclass{article}
% The file ijcai07.sty is the style file for IJCAI-07 (same as ijcai05.sty).
%\usepackage{ijcai07}
%\usepackage{ijcai09}
%\usepackage{proceed2e}
% Use the postscript times font!
%\usepackage{times}

%\documentclass[]{article}
%\usepackage{proceed2e}

\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{color}
\usepackage{epsfig}


%\usepackage{pst-node}

\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usepackage{verbatim}

%\ecaisubmission   % inserts page numbers. Use only for submission of paper.
                  % Do NOT use for camera-ready version of paper.

%\documentclass[letterpaper]{article}
%\usepackage{aaai}
%\usepackage{times}
%\usepackage{helvet}
%\usepackage{courier}
%\usepackage{amsthm}
%\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{amsfonts}
%\usepackage{graphicx}
%\usepackage{epsfig}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{defi}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{rem1}{Remark}\newenvironment{rem}{\begin{rem1}\rm}{\end{rem1}}
\newtheorem{ex}{Example}
\newtheorem{cor}{Corollary}
%\newtheorem{lemma}{Lemma}
%\newtheorem{property}{Property}

%\newtheorem{Demonstration}{Proof}
%\renewcommand{\theDemonstration}{}
%\newenvironment{proof}{\begin{Demonstration}}{\hfill\rule{2.5mm}{2.5mm}\end{Demonstration}}

\newif\iffull
\fullfalse
\newif\ifpav
\pavfalse

\newif\ifpr
\prfalse
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\A}{{\mathcal{A}}}
\newcommand{\B}{{\mathcal{B}}}
\newcommand{\C}{{\mathcal{C}}}
\newcommand{\D}{{\mathcal{D}}}
\newcommand{\E}{{\mathcal{E}}}
\newcommand{\F}{{\mathcal{F}}}
\newcommand{\K}{{\mathcal{K}}}
\newcommand{\PK}{{\mathcal{P}}}
\newcommand{\I}{{\mathcal{I}}}
\newcommand{\G}{{\mathcal{G}}}
\newcommand{\HA}{{\mathcal{H}}}
\newcommand{\LA}{{\mathcal{L}}}
\newcommand{\OA}{{\mathcal{O}}}
\newcommand{\R}{{\mathcal{R}}}
\newcommand{\SA}{{\mathcal{S}}}
\newcommand{\U}{{\mathcal{U}}}
\newcommand{\V}{{\mathcal{V}}}
\newcommand{\X}{{\mathcal{X}}}
\newcommand{\T}{{\mathcal{T}}}
\newcommand{\PA}{{\mathcal{P}}}

\newcommand{\AF}{{\langle\A,\mathtt{Def}\rangle}}
\newcommand{\Def}{{\mathtt{Def}}}
\newcommand{\att}{{\mathtt{Att}}}
\newcommand{\paf}{(\A, \R)}
\newcommand{\pafs}{(\A, \R_s)}
\newcommand{\pafo}{(\A, \R_o)}
\newcommand{\dt}{<\A, \R, O>}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\conferenceinfo{WOODSTOCK}{'97 El Paso, Texas USA}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\title{%1) Argumentation, Decision and Preference\\
%Augmented
Extending Argumentation to make good Decisions }
\author{Yannis Dimopoulos\inst{1} \and Pavlos Moraitis \inst{2}  \and
Leila Amgoud \inst{3}}

\institute{Dept. of Computer Science, University of Cyprus,
Nicosia, Cyprus \email{yannis@cs.ucy.ac.cy}
%
\and Laboratory of Informatics Paris Descartes (LIPADE), Paris
Descartes University, Paris, France\\
\email{pavlos@mi.parisdescartes.fr}
%
\and Paul Sabatier University, Toulouse, France\\
\email{amgoud@irit.fr}}




%\institute{University of Cyprus, 75 Kallipoleos Str. 1678,
%Nicosia-Cyprus}  \and Pavlos Moraitis\institute{Paris Descartes
%University, 45 rue des Saints-P\`eres 75270, Paris-France} \and
%Leila Amgoud\institute{Paul Sabatier University, 118 route de
%Narbonne 31062, Toulouse-France}}


\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}

Argumentation has been acknowledged as a powerful mechanism for
automated decision making. In this context several recent works
have studied the problem of accommodating preference information
in argumentation. The majority of these studies rely on Dung's
abstract argumentation framework and its underlying acceptability
semantics.

In this paper we show that Dung's acceptability semantics, when
applied to a preference-based argumentation framework for decision
making purposes, may lead to counter intuitive results, as it does
not take appropriately into account the preference information. To
remedy this we propose a new acceptability semantics, called
\emph{super-stable extension} semantics, and present some of its
properties.
%
Moreover, we show that argumentation can be understood as a
multiple criteria decision problem, making in this way results
from decision theory applicable to argumentation.

\end{abstract}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{Delphi theory}

%\keywords{ACM proceedings, \LaTeX, text tagging}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


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

In many decision making situations we are confronted with a set of
alternatives or options each of which has its own advantages that
can be expressed as different arguments supporting that
alternative. For instance, in a car purchase scenario, one
argument that supports small cars is that they have low running
cost, while another argument that favors big cars is that they
have better safety features. The final decision is usually based
upon the preferences one has over the arguments, or more generally
how arguments relate to each other.

%Automated decision making is an important issue in artificial
%intelligence and particularly in agent based computing.

It is therefore not surprising that during the last years,
argumentation has been acknowledged as a powerful mechanism for
automating the decision making process of autonomous agents.
Several recent works (see e.g.
\cite{kakas03,uai05,AmDiMo2008.1,geffner,aaai06}) have emphasized
the role of agents' preferences in the evaluation of their
arguments within a particular class of argumentation frameworks
called \emph{preference-based argumentation} frameworks. The
majority of these frameworks are using the acceptability semantics
of the Dung's abstract argumentation framework \cite{dung}.



In \cite{DiMoAm2008.1}, it was shown that preference-based
argumentation under the stable extension semantics is essentially a
method for making decisions that are supported by "good" or "strong"
arguments. Roughly speaking, a set of arguments $E$ is a stable
extension if every argument of $E$ is strictly preferred to any
other argument that is not included in $E$.

In this work we show that the stable extensions semantics of
Dung's framework when applied to decision making may lead to
counterintuitive results and therefore fail to deliver the correct
conclusions.

More precisely, we show that stable extensions consider as equally
good two sets of arguments (and therefore the options they
support), although for every argument of the second set, the first
set contains a more preferred argument. One may understand that in
this case the agent could randomly select an option that is
supported either by an argument from the first or the second set
and this could be a wrong decision if these arguments support
incorrect conclusions. This problem relates to a similar problem
identified independently by Horty in \cite{Horty01} in the context
of the use of argumentation for defeasible reasoning. For this
reason we propose a new semantics called \emph{super-stable}
extension which allows to fix this problem.

%In this paper we propose a new semantics called
%\emph{super-stable} extension and we show that by applying this
%new semantics it is now possible to draw the counter intuitive
%results and to keep only the correct conclusions. .....

Finally, in this paper we show the correspondence between
argumentation and multi-criteria decision making. Then we
emphasize that an aggregation method like {\em regime}
\cite{RegimeOrig} can be an alternative approach for defining a
ranking on the set of arguments supporting the options and
consequently on the options themselves.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basics of argumentation}\label{basic}

Argumentation is a reasoning model based on the following main
steps: i) constructing \emph{arguments} and counter-arguments, ii)
defining the \emph{strengths} of those arguments, and iii)
 defining the \emph{justified conclusions}.
%
Argumentation systems are built around an underlying logical
language and an associated notion of logical consequence, defining
the notion of argument. The argument construction is a monotonic
process: new knowledge cannot rule out an argument but only gives
rise to new arguments which may interact with the first argument.
Arguments may be conflicting for different reasons.
%
\begin{defi}[\textbf{Argumentation system} \cite{dung}]
   An \emph{argumentation system} is a pair $T$ = $(\A$, $\R)$.
   $\A$ is a set of arguments and $\R$ $\subseteq$ $\A$ $\times$ $\A$ is an attack relation.
   We say that an argument $a$ attacks an argument $b$ iff ($a, b$) $\in$ $\R$.
\end{defi}



Among all the arguments, it is important to know which arguments to
keep for inferring conclusions. In \cite{dung}, different
acceptability semantics were proposed. The basic idea behind these
semantics is the following: for a rational agent, an argument $a_i$
is acceptable if he can defend $a_i$ against all attacks. All the
arguments acceptable for a rational agent will be gathered in a
so-called \emph{extension}. An extension must satisfy a consistency
requirement and must defend all its elements.
%
%
\begin{defi}[\textbf{Conflict-free, Defence} \cite{dung}]
Let $\B$ $\subseteq$ $\A$, and $a_i \in \A$.
\begin{itemize}
   \item $\B$ is \emph{conflict-free} iff $\nexists$ $a_i$, $a_j$ $\in$
         $\B$ s.t. $(a_i,a_j)$ $\in \R$.
   \item $\B$ \emph{defends} $a_i$ iff $\forall$
         $a_j$ $\in$ $\A$, if $(a_j,a_i)$ $\in \R$, then $\exists$ $a_k$
         $\in$ $\B$ s.t. $(a_k,a_j)$ $\in \R$.
\end{itemize}
\end{defi}
%
The main semantics introduced by Dung are summarized in the
following definition.
%
\begin{defi}[\textbf{Acceptability semantics} \cite{dung}]\label{sem}
    Let $\B$ be a conflict-free set of arguments.
%
    \begin{itemize}
            \item $\B$ is \emph{admissible} iff it defends any argument in $\B$.
            \item $\B$ is a \emph{preferred} extension iff it is a maximal (w.r.t $\subseteq$)
                        admissible extension.
            \item $\B$ is a \emph{stable} extension iff it is a preferred extension that attacks any
                  argument in $\A \backslash \B$.
    \end{itemize}
\end{defi}

\begin{ex}\label{uni}
    Let $T$ = $(\A$, $\R)$ be an argumentation theory where
    $\A= \{\alpha_1, \alpha_2, \alpha_3, \alpha_4 \}$
   is the set of the arguments and $\R=\{(a_1,a_2), (a_2,a_1),
   (a_1,a_4),(a_2,a_3)\}$ is the set of
    attacks. This argumentation theory has two stable extensions
    $\E_1$ = $\{\alpha_1, \alpha_3\}$
    and $\E_2$ = $\{\alpha_2, \alpha_4\}$
\end{ex}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preference-based Argumentation Framework: Properties and Limitations}
\label{basic}

In \cite{AC:98} the basic argumentation framework of Dung was
extended into \emph{preference-based argumentation theory (PBAT)}.
The framework was further developed and studied in
\cite{DiMoAm2008.1}. The basic idea of a PBAT is to consider two
binary relations between arguments:

\begin{enumerate}
    \item A \emph{conflict} relation, denoted by $\C$, that is based on
                the logical links between arguments.
    \item A \emph{preference} relation, denoted by $\succeq$, that captures the idea that
                some arguments are stronger than others. Indeed, for two arguments
                $a, b \in \A$, $ a \succeq b$ means that $a$ is at least as good as
                $b$. The relation $\succeq$ is assumed to be a
                partial pre-order (that is \emph{reflexive} and \emph{transitive}).
                The relation $\succ$ denotes the corresponding strict relation. That is,
                $a \succ b$ iff $a \succeq b$ and $b \not \succeq a$.
\end{enumerate}

The two relations are combined into a unique attack relation,
denoted by $\R$, and the Dung's semantics are applied on the
resulting framework. In what follows, we focus on a particular
class of PBATs, presented in \cite{DiMoAm2008.1}, where the
conflict relation $\C$ is \emph{irreflexive} and \emph{symmetric}.




\begin{defi}[\textbf{Preference-based Argumentation
Theory (PBAT)}] (\cite{AmDiMo2008.1}) \label{PBAT} Given an
irreflexive and symmetric conflict relation $\C$ and a preference
relation $\succeq$ on a set of arguments $\A$,  a {\em
preference-based argumentation theory} ({\em PBAT}) on $\A$ is an
argumentation system $T=(\A,\R)$, where $(a, b) \in \R$ iff $(a,
b) \in \C$ and $b \not \succ a$.
\end{defi}

It follows directly from the definition that if $(a, b) \in \C$
and $a \succeq b$ and $b \not \succeq a$, then $(a, b) \in \R$.
Moreover, if $(a, b) \in \C$ and $a, b$ are either indifferent or
incompatible in $\succeq$, then $(a, b) \in \R$ and $(b, a) \in
\R$. Also note that if $(a, b) \in \C$, then either $(a, b) \in
\R$ or $(b, a) \in \R$. Finally, if $(a, b) \in \R$ and $(b, a)
\notin \R$, then $a \succ b$.



The following example illustrates some features of PBATs.


\begin{ex}
Let $\A =\{a, b, c, d \}$ be a set of arguments, and $\C$ the
conflict relation on $\A$ defined as $\C=\{ (a, b), (b, a), (b,
c), (c, b), (c, d), (d, c) \}$. Moreover, let the preference
relation $\succeq$ contain transitive closure of the set of pairs
$a \succeq b$, $b \succeq c$, $c \succeq d$, and $d \succeq c$.
The corresponding PBAT is $T=(\A,\R)$, where $\R=\{ (a, b), (b,
c), (c, d), (d, c) \}$. Theory $T$ has two stable extensions,
$E_1=\{ a, c \}$ and $E_2=\{a, d \}$.
\end{ex}




In \cite{AmDiMo2008.1} the impact of the preference relation on an
argumentation system was studied. After defining a relation $\rhd$
on the powerset $2^{\A}$ of the arguments of a PBAT $T$ = $\paf$, it
was shown that the stable extensions of $T$ correspond to the most
preferred elements of $2^{\A}$ wrt this relation.


\begin{defi} \label{ECAI-def1} (\cite{AmDiMo2008.1})
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$.
    % the relation $\rhd$ is defined on $2^{\A}$ as follows.
    If $A_1, A_2 \in 2^{\A}$, with $A_1 \not = A_2$, then $A_1 \rhd A_2 $
%    The ranking $\rhd$ induced by $\succeq$ on the set
%    $2^{\A}$ defines $A_1 \rhd A_2 $, for $A_1, A_2 \in 2^{\A}$, with $A_1 \not = A_2$,
    iff one of following holds:
    \begin{itemize}
    \item $A_1 \supset A_2 $
    \item
%    \begin{itemize}
%    \item
    for all $a, b$ such that $a \in A_1 \setminus A_2$
    and $b \in A_2 \setminus A_1 $, it holds that $a \succ b$
%    and
%    \item $\forall a \in A_1$, $\neg \exists b \in A_2$ s.t. $b \succ a$
%    \end{itemize}
    \end{itemize}
\end{defi}


The exact correspondence between the relation $\rhd$ and stable
extensions is as follows.


\begin{thm}\label{rank-theo} (\cite{AmDiMo2008.1})
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ and a conflict relation $\C$. $E$ is a stable extension of $T$ iff
%    it is a maximal element of $ \rhd $ among the conflict-free
%    elements of $2^{\A}$.
    there are no arguments $a, b \in E$ s.t. $(a, b) \in \C$, and for all $A \in
    2^{\A}$ such that $A \rhd E$, there are $a_1, a_2 \in A$ such
    that $(a_1, a_2) \in \C$.
\end{thm}


The example below illustrates the link between  $\rhd$ and stable
extensions.

\begin{ex}
Let $T$ = $\paf$ be a PBAT with $\A=\{a, b, c\}$ and $\R$ composed
from the conflict relation $\C=\{ (a, b), (b ,a) (a, c), (c, a)
\}$ and preference relation that contains the pairs $a \succ b$
and $a \succ c$, and marks all other pairs of arguments as
indifferent. The relation $\rhd$ on $2^{\A}$ induced by $\succeq$
contains the pairs $\{a\} \rhd \{b, c\} $, $\{a\} \rhd \{b\} $,
$\{a\} \rhd \{ c\} $. Since the sets $\{a, b, c \}$, $\{a, b \}$,
$\{a, c\}$ are ruled out by $\C$, the set $E=\{a \}$ is the stable
extension of $T$.

\end{ex}


One feature of the $\rhd$ relation is that it may {\em not be
transitive}. Consider for instance the theory of the previous
example, and observe that $\{a, b \} \rhd \{b, c \} \rhd \{ c \}$.
However, it is not the case that $\{a, b \} \rhd \{ c \}$.

The second important observation, which is the main focus of this
work, relates to the conclusions sanctioned by preference-based
argumentation under the stable model semantics. The following
example, borrowed from \cite{Horty01}, shows clearly that these
results can be counterintuitive even in simple cases.



\begin{ex} \label{counter-trans-ex}
The story of the example is about conclusions that can been drawn
regarding the financial situation of a person based on arguments
built on information about her occupation and residence. Let's
suppose that lawyers are, in general, considered to be wealthy, but
a certain subclass, the pubic defenders, are considered not to be.
Consider now an area in Paris -say, Passy - containing a large
number of expensive private homes along with a much smaller number
of middle-income rental properties. Thus the residents of Passy can
be generally considered to be wealthy although the renters, are
considered to not to be. Assume that Ann is a public defender
($PDa$), and therefore a lawyers ($La$), who rents in Passy ($Ra$),
and is therefore a resident of Passy ($Pa$).

If we assume that $Wa$ represents the proposition that Ann is
wealthy, the arguments that can be generated in an underlying
propositional language from the above story are $a_1=\{PDa, PDa
\longrightarrow La, La \longrightarrow Wa \}$, $a_2=\{ PDa, PDa
\longrightarrow \neg Wa \}$  $a_3=\{Ra, Ra \longrightarrow Pa, Pa
\longrightarrow Wa\}$, $a_4=\{ Ra, Ra \longrightarrow  \neg Wa\}$.

%This story can be formally presented as follows. Let $\A=\{(\{PDa,
%PDa \longrightarrow La, La \longrightarrow Wa\}, Wa), (\{Ra, RDa
%\longrightarrow Ba, Ba \longrightarrow Wa\}, Wa), \{PDa, PDa
%\longrightarrow Wa\}, \neg Wa), (\{Ra, Ra \longrightarrow Wa\},
%\neg Wa)\}$

From the above arguments we generate the PBAT $T$=$\paf$, where
$\A=\{a_1, a_2, a_3, a_4 \}$. The attack relation $\R$ is composed
from the conflict relation $C=\{ (a_1, a_2), (a_2, a_1), (a_1,
a_4), (a_4, a_1), (a_3, a_2), (a_2, a_3), (a_3, a_4), (a_4, a_3)
\}$, and the preference relation $\succeq$ that is defined as $a_2
\succ a_1$ and $a_4 \succ a_3$, whereas all other pairs of
arguments are incomparable.


Theory $T$ has two extensions, namely $E_1 =\{a_1, a_3 \}$ and
$E_2 =\{ a_2, a_4 \}$. The first extension supports the conclusion
that Ann is wealthy, whereas the the second that she is not.
Intuitively however one would conclude that Ann is not wealthy. In
other words we could argue that the second extension is more
preferred than the first, as for every argument of the first it
contains a more preferred argument.

%\\
% Let $T$ = $\paf$ be a PBAT with $\A=\{a, b, c, d\}$ and $\R$
%composed from the conflict relation $C=\{ (a, b), (b, c), (c, d),
%(d, a) \}$ and preference relation $\succeq$ that is defined as $b
%\succ c$ and $d \succ a$, whereas all other pairs of arguments are
%incomparable.
%
% \iffull
The relation $\rhd$ on the subset of $\A$ with two
elements is depicted in figure \ref{f1}.
% \fi
%
% Theory $T$ has two extensions, namely
%$E_1 =\{a, c \}$ and $E_2 =\{ b, d \}$. Observe that one could
%argue that the second extension is more preferred than the first,
%as for every argument of
%the first it contains a more preferred argument.\\
 Note again that $\rhd$ is not transitive.  Indeed, it holds that $\{
a_2, a_4\} \rhd \{ a_2, a_3 \}$ and $\{ a_2, a_3\} \rhd \{ a_1,
a_3 \}$, but $\{ a_2, a_4\}$ $\not \rhd \{ a_1, a_3 \}$. Although,
$a_2 \succ a_1$ and $a_4 \succ a_3$, the stable model semantics
does not render $\{ a_2, a_4\}$ better than $\{ a_1, a_3 \}$,
because $a_2 \not \succ a_3$ and $a_4 \not \succ a_1$.
\end{ex}


%\iffull

\begin{figure}[t]\label{f1}
%\centerline {
\begin{tikzpicture}[->,>=stealth',shorten >=0.8pt,auto,node distance=1.8cm,semithick]
  \tikzstyle{every state}=[fill=gray,draw=none,text=black]

  \node[state] (A)                    {$a_2 a_3$};
  \node[state] (B) [right of=A]  {$a_1 a_3$};
  \node[state] (C) [below right of=A] {$a_1 a_4$};
  \node[state] (D) [below right of=B] {$a_2 a_4$};
  \node[state] (E) [right of=B] {$a_3 a_4$};
  \node[state] (F) [right of=D] {$a_1 a_2$};


  \path (A) edge  (B);
%  \path (D) edge  (B);
  \path (C) edge  (B);
  \path (D) edge  (C);
  \path (D) edge  (A);
\end{tikzpicture}
%}
\caption{The preference relation induced on sets of arguments.}
\end{figure}

%\fi

The main purpose of this work is to provide a preliminary  study
of the problem of the conclusions sanctioned by the
state-of-the-art argumentation, and identify possible solutions by
borrowing ideas from decision theory.


\section{Preference-based Argumentation revisited}

As we noted in section \ref{basic}, the stable model semantics can
lead to counter-intuitive results. To remedy the situation we
present a new semantics for preference-based argumentation called
{\em super-stable} extensions semantics. The main idea is to only
accept conclusions drawn under the stable model semantics from a
PBAT $T$ that correspond to the conclusions that are sanctioned by
some other PBAT $T'$ which is obtained from $T$ by removing
incomparability. Therefore, the new semantics may differ from the
standard stable model semantics only on theories with
incomparability. As we will discuss in the next section theories
without incomparability always sanction the correct conclusion
under the stable extension semantics.


Before we proceed to the definition of the new semantics, we
recall some useful concepts. A relation $\succeq$ on a set $S$ is
\textit{total } if for all $a,b \in S$ with $a \not = b$, $a
\succeq b$ or $b \succeq a$. A \textit{strict total order} on a
set $S$ is an asymmetric (hence irreflexive), transitive and total
relation on $S$. The notion of an \emph{extension} of a relation
is used in decision theory and economics eg. (\cite{hansson},
\cite{donaldson})


\begin{defi}
 A binary relation $\succeq_E$ on $S$ is an \textit{extension} of a
  pre-order $\succeq$ on $S$ if $\succeq_E$ is a pre-order on $S$ such that
  $\succeq_E \supseteq \succeq$ and for all $a,b \in S$ if $a \succ
  b$ then $a \succ_E b$. An extension of a pre-order $\succeq$  that is
  complete (ie., for all $a,b \in S$, $a \succeq b$ or $b \succeq a$)
  is called \textit{ordering extension} of $\succeq$.
\end{defi}

 Hansson \cite{hansson} has shown that every pre-order has an ordering
  extension. Moreover, Donaldson and Weymark \cite{donaldson} proved that
%  any pre-order on $S$ is the
%  intersection of orderings of $S$. More specifically,
  a pre-order is the intersection of its ordering extensions.

\begin{defi}
   A strict total order $\succ_s$ on a set $S$ is a \textit{strict ordering} of a
  total pre-order $\succeq$ if for all $a, b \in S$ if $a \succ b$
  then $a \succ_s b$.\\
  A strict total order is a \textit{strict ordering} of a
  pre-order if it is a strict ordering of one of its
  ordering extensions.
%
\end{defi}


%A \textit{partial order} on $S$ is a reflexive antisymmetric and
%transitive relation on $S$. A \textit{strict partial order} on $S$
%is an irreflexive transitive relation on $S$.

The following definition extends the notions of ordering extension
and strict ordering to the case of PBATs.

%To any pre-order $\succeq$ we can associate a strict (total)
%preorder $\succ_s$ that is consistent with $\succeq$. This leads to
%the definition of the strict projection of PBAT, which is a follows.



 \begin{defi}
    Let $T$ = $\paf$ be a  PBAT on an underlying pre-order
    $\succeq$ and a conflict relation $\C$. The PBAT $T_o$ = $\pafo$,
    on an underlying relation $\succeq_o$ and the conflict relation $\C$, is a
    {\em ordering completion} of $T$ if $\succeq_o$ is an ordering
    extension of $\succeq$. The PBAT $T_s$ = $\pafs$, on an underlying
    relation $\succ_s$ and the conflict relation $\C$, is a
    {\em strict projection} of $T$ if $\succ_s$ is a strict ordering of $\succeq$.
 \end{defi}


The following result that relates the stable extensions of a PBAT
and the stable extensions of its ordering completions and strict
projections is easily provable.


 \begin{prop}
    Let $T$ be a PBAT, $T_o$ one of its ordering completions,
    and $T_s$ one of its strict projections.
    If $E_o$ is a stable extension of $T_o$, then it is also a
    stable extension of $T$. Moreover, if $E_s$ is a stable extension of $T_s$,
    then it is also a stable extension of $T$.
 \end{prop}

However, it is not the case that a stable extension of $T$ is a
stable extension of some $T_o$ built on a pre-order $\succ_o$ that
is an ordering extension of $\succeq$. Consider for instance again
the theory of example 4, and its stable extension $E_1 =\{a_1, a_3
\}$. To see that there is no PBAT $T_o$ which is an ordering
completion of $T$ and has $E_1$ as a stable extension, observe
that for $E_1$ to be a stable extension it must be the case that
$a_1 \succeq a_4$ and $a_3 \succeq a_2$. However, together with
$a_2 \succ a_1$ these would mean that $a_3 \succeq a_4$, which is
impossible given that $a_4 \succ a_3$.
%Therefore, there can not be an ordering extension of $T$ that has
%$E_1$ as its stable extension.

%and all the strict preorders consistent with $\succeq$, namely: $b
%\succ_1 d \succ_1 a \succ_1 c$, $b \succ_2 d \succ_2 c \succ_2 a$,
%$d \succ_3 b \succ_3 a \succ_3 c$, $d \succ_4 b \succ_4 c \succ_4
%a$. Observe that all the strict projections of $T$ have $E_2$ as
%their stable extension. Therefore, the counterintuitive extension
%$E_1$ is not a stable extension of any of the strict projections of
%$T$.

We now proceed with the definition of the new semantics for
preference-based argumentation. As noted earlier, the basic idea
is to only accept a set of arguments as an extension of a PBAT $T$
if this set is a stable extension of an ordering completion of
$T$. More formally the concept is defined as follows.



 \begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ and conflict relation $\C$.  A stable extension $E$ of $T$
    is a {\em super-stable} extension of $T$ if it is the stable extension of
    an ordering extension of $T$.
 \end{defi}

By the results of \cite{hansson} we know that every pre-order has
an ordering extension. Therefore, every PBAT has an ordering
completion which is itself a PBAT. From \cite{DiMoAm2008.1}, we
know that every PBAT has a stable extension. By combining these
two results we obtain the following property for super-stable
extensions.

 \begin{prop}
 Every PBAT has a super-stable extension.
 \end{prop}



\section{Theories without incomparability}

If a PBAT $T$ contains no incomparability, $T$ is an ordering
completion of itself. Therefore, any stable extension of $T$ is by
definition a super-stable extension of $T$. In this section we
prove that for this class of theories a correspondence holds
between their stable extensions and the stable extensions of their
strict projections.

For a PBAT without incomparability,  $T$ = $\paf$, we define the
{\em level} of argument $a \in \A$, denoted by $l(a)$, recursively
as follows


\begin{itemize}
  \item $l(a) = 1$ for all $a$ such that there is no $b \in \A$ s.t. $b \succ a$
  \item $l(a)=k$ for all $a$ such that for all $a' \in \A$ s.t. $a'
  \succ a$ it holds that $l(a') < k$, and $\exists a'' \in \A$ s.t. $a'
  \succ a$ and $l(a') = k-1$
\end{itemize}

The following lemma relates the level of  arguments with relation
$\succ$ and will be used in the proof of the main result of this
section (proposition \ref{pro-noinco} below).

\begin{lemma} \label{lemma1}
    Let $T$ = $\paf$ be a PBAT without incomparability on an underlying pre-order
    $\succeq$. For every $a, b \in \A$, $l(a) < l(b)$ iff $a \succ b$.
\end{lemma}
\begin{proof}
The property that for every $a, b \in \A$ if $a \succ b$ then $l(a)
< l(b)$, follows directly from the definition of the level of an
argument. We prove now that if $l(a) < l(b)$ then $a \succ b$.
Assume $a, b \in \A$ with $l(a) < l(b)$. Clearly it can not be the
case $b \succ a$, because then $l(b) < l(a)$. Assume that $a \succeq
b$ and $b \succeq a$, and $l(b)=m$ (hence, $l(a) < m$). Then, there
must be $c \in \A$ s.t $l(c)=m-1$ and $c \succ b$. Therefore, it
must be the case that $c \succ a$, and hence $l(a) \geq m$. But this
contradicts $l(a) < m$. Therefore it holds that $a \succ b$. \qed
\end{proof}


A direct consequence of the previous lemma is that $l(a) \leq
l(b)$ iff $a \succeq b$. Also note that since a super-stable
extension of a PBAT $T$ = $\paf$ is also a stable extension of
$T$, it holds that for all $a \not \in E$ there exist $b \in E$
such that $(b, a)\in \R$. From the above we conclude that for all
$a \not \in E$ there exist $b \in E$ such that $(a, b) \in \C$ and
$l(b) \leq l(a)$.
%
Note the above property does not hold in general for theories that
contain incomparability.


 \begin{prop}\label{pro-noinco}
Let $T$ be a PBAT without incomparability. Every stable extension of
$T$ is a stable extension of some strict projection of $T$.
 \end{prop}
%
\begin{proof}
We prove the claim by defining a strict projection of $T$,
$T_s=\pafs$, for which $E$ is a stable extension.
%
Let $\succ_s^{E^+}$ be a strict projection on the arguments of $E$.
Similarly, let $\succ_s^{E^-}$ be a strict projection on the
arguments of $\A \setminus E$. Finally, let $\succ_s^{E^{+,-}}$ be
the binary relation on $(E \times (\A \setminus E)) \cup ((\A
\setminus E) \times E ) $ such that for any pair of arguments $a \in
E$ and $b \not \in E$
%
\begin{itemize}
  \item if $l(a) > l(b)$ then $b \succ_s^{E^{+,-}} a$
  \item if $l(a) \leq l(b)$ then $a \succ_s^{E^{+,-}} b$
\end{itemize}
%
where $l(a)$ is the level of argument $a$ in theory $T$. Define
$\succ_s = \succ_s^{E^+} \cup \succ_s^{E^-} \cup
\succ_s^{E^{+,-}}$.\\
We first show that $\succ_s$ is strict total order. It is easy to
verify that $\succ_s$ is asymmetric and total by construction. We
show that $\succ_s$ is transitive. Let $a, b, c \in \A$, such that
$a \succ_s b$ and $b \succ_s c$. We need to show that $a \succ_s
c$. We proceed by case analysis. For the case where $a, b, c \in
E$ or $a, b, c \in \A \setminus E$, transitivity follows by
construction.\\
%
Assume now that $a \in E$ and $b, c \not \in E$. Then, by
construction, $l(a) \leq l(b)$. Moreover, since  $b \succ_s c$, by
lemma \ref{lemma1}, it must be the case $l(b) < l(c)$. Hence,
$l(a) < l(c)$, which, again by lemma \ref{lemma1}, means that $a
\succ_s c$. The case where $a \in E$, $b \not \in E$, $c \in E$
is similar.\\
%
Now suppose  that $a,b \in E$, and $c \not \in E$. Since $a
\succ_s b$, by lemma \ref{lemma1}, we obtain that $l(a) <l(b)$.
Moreover, by construction, it must hold that $l(b) \leq l(c)$.
Hence, $l(a) < l(c)$, and therefore $a \succ_s c$.\\
The remaining cases where $a \not \in E$ can be proved
analogously.

Finally, we prove that $E$ is a stable extension of $T_s=\pafs$.
First note that $E$ is conflict free. Now assume that $a \not \in E$
and define $D(a)=\{b | b \in E$ and $(b, a) \in \R\}$. Since $E$ is
a stable extension, it must be $D(a) \not = \emptyset$. Let $b \in
D(a)$, and assume that $(b, a) \not \in \R_s$. By construction, it
must hold that $l(a) < l(b)$, which by lemma \ref{lemma1} implies $a
\succ b$. This however contradicts $b \in D(a)$. Therefore, $(b, a)
\in \R_s$, which means that $E$ is a stable extension of $T_s$. \qed

\end{proof}


By combining the definition of a super-stable extension with
proposition \ref{pro-noinco} we obtain the following strong property
regarding the super-stable extensions of theories without
incomparability.

\begin{prop}
Every super-stable extension of a PBAT $T$ that contains no
incomparability is a stable extension of some strict projection of
$T$.
\end{prop}

%\textbf{Computational issues??}






\iffull


\subsection{Alternative definitions of super-stable extensions}

{\bf We tried several alternative characterizations of semi-stable
extensions, but none works. A new proposal is the following. It has
not been checked yet}.



Given a PBAT $T$ = $\paf$ built on a conflict relation $\C$, and $a
\in \A$, $S \subseteq \A$, we define $C(a,S)=\{ n| (n, a) \in \C, n
\in S\}$. We also define an attack relation $\R_{SS}$ where $(a, b)
\in \R_{SS}$ iff $a \in C(b,S)$ and $b \not \succ a$.

\begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ and conflict relation $\C$.  The set $E$ is a {\em
    super-stable} extension iff $E$ is a stable extension of $T$ and
    $\forall a,a' \not \in E$, $\forall b \in C(a,E)\cup C(a',E)$ such that $((a,b) \in \R_{SS}$ and
    $(b,a) \not \in R_{SS})$ and  $((a',b) \in \R_{SS}$ and
    $(b,a') \not \in R_{SS})$, $\exists d,d' \not \in E, \exists c \in C(d,E), \exists c' \in C(d',E)$ s.t. (($c,d) \in
    \R_{SS}$ and $(d,c) \not \in \R_{SS})$ and $((c',d') \in
    \R_{SS}$ and $(d',c') \not \in \R_{SS})$ and $c \neq c'$, $d
    \neq d'$
 \end{defi}







\section{Preference-based Argumentation revisited}

In this section we propose a new semantics for ..... and study some
of its properties.


 \begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$.  The set $E$ is a {\em
    super-stable} extension iff $E$ is a stable extension of $T$ and \textbf{if} $\exists y \not \in E$,
    $\exists x \in E$ s.t. $y \succ x$ and $\neg \exists z \in E$ s.t. $z \succ y$,
    \textbf{then} $\exists q \in E$,
    $\exists p \not \in E$ s.t. $q \succ p $, and $\neg \exists r \not \in E$
    s.t. $r \succ q$.
 \end{defi}

 \begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$.  The set $E$ is a {\em
    super-stable} extension iff $E$ is a stable extension of $T$ and
    there are no sets $A$ and $B$ such that
   \begin{itemize}
   \item  $A \subseteq \A \setminus E$, $B \subseteq E$
   \item  $A$ is conflict free, and if $(a, b) \in \C$ for $a
   \in A$ and $b \in E$, then $b \in B$
   \item there exists $a \in A$, $b \in B$ s.t. $a \succ b$
   \item there is no $b \in B$, $a \in A$ s.t. $b \succ a$
   \end{itemize}
 \end{defi}

\begin{ex}
This is counterexample to the definition above. Assume $\A = \{a,b,
c, d\}$ and the preferences $d \succ a$, $b \succ c$ and all other
pairs of arguments are incomparable. Also let $\C=\{ (a,c), (a,d),
(b, c), (b, d) \}$. The theory has two extensions, $E_1 =\{a, b \}$
and $E_2=\{c, d \}$, both of should be (??) super-stable. Note that
$E_1$ violates the above definition, because there exist $A=\{d \}$,
$B=E_1$ with $d \succ a$ and $a \not \succ d$ and $b \not \succ d$.
\end{ex}


An alternative definition could be.

 \begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$.  The set $E$ is a {\em
    super-stable} extension iff $E$ is a stable extension of $T$ and
    there are no sets $A$ and $B$ such that
   \begin{itemize}
   \item  $A \subseteq \A \setminus E$, $B \subseteq E$
   \item  $A$ is conflict free, and for all $a
   \in A$ and $b \in E$ with $(a, b) \in \C$ then $b \in B$
   \item For each $c \not \in E$ s.t. for all $b \in E$ with $(b, c)
   \in \C$ it holds that $b \in B$, then $c \in A$
   \item there exists $a \in A$, $b \in B$ s.t. $a \succ b$
   \item there is no $b \in B$, $a \in A$ s.t. $b \succ a$
   \end{itemize}
 \end{defi}


Given a PBAT $T$ = $\paf$ built on a conflict relation $\C$, and $a
\in \A$, $S \subseteq \A$, we define $C(a,S)=\{ n| (n, a) \in \C, n
\in S\}$.

  \begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ and conflict relation $\C$.  The set $E$ is a {\em
    super-stable} extension iff $E$ is a stable extension of $T$, and for
    every $a \not \in E$, it holds that either
      \begin{itemize}
    \item $\exists b \in  C(a,E)$ s.t. $b \succ a$, or
%
    \item $\neg \exists b \in C(a,E)$ such that $a \succ b$, and
    $\forall c \not \in E$ s.t. $\exists d \in C(a,E)$ with $d \succ
    c$, either $(a, c) \not \in \C$ or $\exists d' \in E$, $d' \not \in C(a,E)$ with $d' \succ c$
    \end{itemize}
 \end{defi}


Given a PBAT  $T$ = $\paf$, we define $T^A$ = $(\A, \R^A)$, where
$\R^A= R \setminus \{ (a, b) | (a, b) \in \R$ and $ (b,a) \in \R
\}$. We call $T^A$ the {\em asymmetric} sub-theory of $T$.  By the
properties proved in \cite{DiMoAm2008.1}, we know that the graph of
$T^A$ is a directed acyclic graph (DAG). It is well known fact that
a DAG contains at least one node with no incoming edges.

Given a PBAT  $T$ = $\paf$, we define the {\em level} of argument $a
\in \A$ recursively as follows


\begin{itemize}
  \item $l(a) = 1$ for all $a$ such that there is no $b \in \A$ s.t. $b \succ a$
  \item $l(a)=k$ for all $a$ such that for all $a' \in \A$ s.t. $a'
  \succ a$ it holds that $l(a') < k$, and $\exists a'' \in \A$ s.t. $a'
  \succ a$ and $l(a') = k-1$
\end{itemize}

\begin{lemma} \label{found-lemma}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ that {\bf contain no incomparability} and conflict relation $\C$.
    For every $a, b \in \A$, if $l(a) < l(b)$ then $a \succ b$.
\end{lemma}

The following result characterizes a fundamental property of
super-stable extensions.

\begin{lemma} \label{found-lemma}
     A stable extension $E$ of a PBAT $T$ = $\paf$ is a super-stable
     extension of $T$ iff for all $a \not \in E$ there exist $b \in
     E$ such that $(a, b) \in \C$ and $l(b) \leq l(a)$.
\end{lemma}

\begin{ex}
This is a counterexample to the previous claim. Assume $\A= \{ a_1,
a_2, b_2, c_2\}$ and the preference relation that $a_2 \succ b2
\succ c_2$, while all other arguments are incomparable. Moreover,
assume that $\C=\{(a_1, b_2), (a_1, c_2), (a_2, b_2), (b_2, c_2)
\}$. There are two stable extensions $E_1 =\{a_1, a_2 \}$ and
$E_2=\{a_2, c_2 \}$. We want (???) both of them to be super-stable.
But observe that $E_2$ does not satisfy the conditions of the
previous lemma. Note that $a_1 \not \in E$ but there is no $n \in E$
such that $(a_1, n) \in \C$ and $l(n) \leq l(a)$.\\
It is possible that the claim holds if there is no incomparability.
\end{ex}


\begin{lemma} \label{lemma1}
     Let $T$ = $\paf$ be a PBAT and $E$ a stable extension of $T$
     that is not super-stable, and $T^A$ = $(\A, \R^A)$ its
     associated asymmetric sub-theory. Then there is $a \in \A$ s.t.
     $\exists b \in \A$ with $(a, b) \in \R^A$, and $\neg \exists c
     \in \A$ such that $(c, a) \in \R^A$.
\end{lemma}
%
\begin{proof}
Clearly the graph of $T^A$ is a DAG, therefore there must be at
least one node that has no incoming edge. We denote by $S$ the
non-empty set of such nodes, and $S'$ the subset of $S$ that
contains nodes with at least one outgoing edge. We show that $S'
\not = \emptyset$. By way of contradiction, assume that $S' =
\emptyset$. Therefore, no node of $S$ has an outgoing edge. If
$S=\A$, then the graph of $T^A$ can not contain any edge, therefore
$\R^A = \emptyset$. This means that all arguments of $\R$ are
symmetric, which contradicts the fact that $E$ is not super-stable.
Therefore, it must be the case that $S \subset \A$. Then, the
sub-graph induced by the non-empty set of arguments $\A \setminus S$
must not contain a node with no incoming edges. This means that this
sub-graph is not a DAG, hence the graph of $T$ is also not a DAG,
contradiction. Therefore, it must be the case that $S' \not =
\emptyset$.
\end{proof}


\begin{thm} \label{super}
     Let $T$ = $\paf$ be a PBAT and $E$ a stable extension of $T$
     that is not super-stable. Then there is a super-stable
     extension $E'$ such that $\exists \alpha \in E' \setminus E$ and
     $\exists b \not \in E'$ with $(\alpha, b) \in \R$,  $(b, \alpha) \not \in \R$
     and $\neg \exists c \in A$ such that $(c, \alpha) \in \R$ and  $(\alpha, c) \not \in \R$.
\end{thm}
%
\begin{proof}
Assume that $E$ is a stable model of $T$ that is not super-stable.
Let $T^A$ = $(\A, \R^A)$ be the associated asymmetric sub-theory of
$T$. By lemma \ref{lemma1} we know that there is $\alpha \in \A$
such that $\exists b \in \A$ with $(\alpha, b) \in \R^A$, and $\neg
\exists c \in A$ such that $(c, \alpha) \in \R^A$. It can not be the
case that $\alpha \in E$, because then $E$ would be super-stable,
hence it holds that $\alpha \not \in E$.

 From $E$ we can can construct a super-stable extension by the
technique that is described below. Let $T_{\alpha^{-}}$ be the
theory induced by the set of arguments $\A \setminus (\{\alpha\}
\cup \Gamma^+(\{\alpha\}))$, and let $M(T_{\alpha^{-}})$ be a
stable extension of $T_{\alpha^{-}}$. From Duchet, we know that
$M(T_{\alpha^{-}})$ always exists.
%
Now define the set $E'= \{\alpha\} \cup M(T_{\alpha^{-}})$. We
will prove that $E'$ is a super-stable extension of $T$.

We first show that $E'$ is conflict-free. Let $b \in
M(T_{\alpha^{-}})$. First note that it can not be the case that
$(\alpha, b) \in \R$, because then $b \in \Gamma^+(\{\alpha\})$.
Moreover, it can not be the case that $(b, \alpha) \in \R$ and
$(\alpha, b) \not \in \R$, because this would mean that $\alpha$ has
an incoming edge in the graph of $T^A$. Moreover, observe that by
construction if $b \not \in E'$, then $b \in \Gamma^+(\{\alpha\}
\cup M(T_{\alpha^{-}}))$. Hence, $E'$ is a stable model.

Finally, $E'$ is super-stable because $\alpha \in E'$ and $\exists b
\not \in E'$ s.t. $(\alpha, b) \in \R$ and $(b, \alpha) \not \in \R$
and $\neg \exists c \not \in E$ s.t. $(c, \alpha ) \in \R$ and
$(\alpha, c ) \not \in \R$.
\end{proof}

A direct consequence of the existence of stable extensions for PBATs
and theorem \ref{super}, is the following corollary.

\begin{cor}
Every PBAT has a super-stable extension.
\end{cor}

\begin{ex}
An example of theorem.
\end{ex}


It seems therefore that there is a need for a different relation
on $2^{\A}$ that satisfies transitivity. This is achieved by the
relation $\rhd_T$ that relaxes the strong requirements of $\rhd$.

\begin{defi}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$. The relation $\rhd_T$ induced by $\succeq$ on the set
    $2^{\A}$ defines $A_1 \rhd_T A_2 $, for $A_1, A_2 \in 2^{\A}$, with $A_1 \not = A_2$,
    iff one of following holds:
    \begin{itemize}
    \item $A_1 \supset A_2 $
    \item
     \begin{itemize}
    \item
    $\forall b \in A_2 \setminus A_1$ $\exists a \in A_1 \setminus A_2$
    s.t. $a \succ b$, and
%    \item $\forall a \in A_1$, $\forall b \in A_2$ it holds that $b \not \succ
%    a$
    \item $\forall a \in A_1 \setminus A_2$, $\forall b \in A_2 \setminus A_1$
    with $a \not = b$, it holds that either $a
    \succeq b$ or $a \not \succeq b$ and $b \not \succeq a$
    \end{itemize}
    \end{itemize}
\end{defi}

\begin{defi}\label{dominance}
    Let $T$ = $\paf$ be a PBAT. The relation $\rhd_T$ defines a \emph{dominance relation} among the
    elements of the set $2^{\A}$. Thus $\forall E,E' \in 2^{\A}$
    we say that $E$ \emph{dominates} $E'$ iff $E \rhd_T E'$.
\end{defi}

The following lemma states an important property of ....

\begin{lemma}
Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ and conflict relation $\C$, and $E$ be a set such that for all $E'$ such that
    $E' \rhd_T E$ it holds that $E'$ is not conflict free. Then,
    for all $a \not \in E$  there must be $b \in E$ such that $b \succeq a$
    or $a \not \succeq b$ and $b \not \succeq a$  and $(a,b) \in \C$.
\end{lemma}
%
\begin{proof}
%We prove the claim inductively on the depth of $a$. Consider an
%argument $a$ of depth 1 (ie. $a$ has in-degree 0) s.t. $a \not \in
%E$
Let $k$ be the smallest level for which there an argument $a$ of
level $k$ such that $a \not \in E$ and there is no $b \in E$ such
that $b \succeq a$ or $a \not \succeq b$ and $b \not \succeq a$  and
$(a,b) \in \C$.
%
%Therefore, for all level $l < k$ and for every argument $a'$ of
%level $l$ if $a' \not \in E$  there must be $b' \in E$ such that $b'
%\succeq a'$ or $a' \not \succeq b'$ and $b' \not \succeq a'$ and
%$(a',b') \in \C$.
%
Let $D(a)=\{n | (a, n) \in \C$, and $n \in E\}$. Define $E'= (E
\setminus D(a)) \cup \{a \}$. First note that $E'$ is conflict free.
We prove now that $E' \rhd_T E$. Note that $E' \setminus E = \{a \}$
and $E \setminus E' = D(a)$. We first show that $a \succ b$ for all
$b \in D(a)$. Assume this is not the case. Then either $ a \not
\succeq b$ or $b \succeq a$. Since it must be the case that $b \in
E$, it can not hold that $b \succeq a$, as this contradicts our
assumption. Therefore it must be the case that $ a \not \succeq b$.
This means that either $b \succ a$, and therefore $b \succeq a$, or
$ b \not \succeq a$. Both cases contradict our assumption about $a$,
therefore it must hold that $a \succ b$ for all $b \in D(a)$. For
this follows that $\forall b \in E \setminus E'$, $a \succeq b$,
which means that $E' \rhd_T E$. Contradiction. Therefore, the claim
holds.
%
\end{proof}



\begin{thm}\label{rank-theo-neq}
    Let $T$ = $\paf$ be a PBAT built on an underlying pre-order
    $\succeq$ and a conflict relation $\C$. The set of arguments $E$ is a
    super-stable extension of $T$ iff
%    it is a maximal element of $ \rhd $ among the conflict-free
%    elements of $2^{\A}$.
    there are no arguments $a, b \in E$ s.t. $(a, b) \in \C$, and for all $A \in
    2^{\A}$ such that $A \rhd_T E$, there are $a_1, a_2 \in A$ such
    that $(a_1, a_2) \in \C$.
\end{thm}
%
\begin{proof}
First assume that $E$ is a super-stable extension. By definition
it is conflict free. Suppose that there is $E' \in 2^{\A}$ s.t.
$E' \supset E$ and $E'$ is conflict free. Then, it is easy to see
that $E$ is not a stable extension and therefore neither a
super-stable extension as well, contradiction. Hence, there can
not be a conflict
free $E'$ such that $E' \supset E$.\\
Suppose now that there is a conflict free set $E'$ (with $E' \not
\supset E$), such that
\begin{itemize}
    \item $\forall b \in E \setminus E'$ $\exists a \in E' \setminus E$
    s.t. $a \succ b$, and
%
    \item $\forall a \in E' \setminus E$, $\forall b \in E \setminus E'$
    with $a \not = b$, it holds that either $a
    \succeq b$ or $a \not \succeq b$ and $b \not \succeq a$
\end{itemize}
%
We show that in this case $E$ is not super-stable.\\
%
 From the first bullet we know that $\exists y \in E', \exists x \in
E$ s.t. $y \succ x$. From the second bullet we know that $\neg
\exists p \in E, \exists q \in E'$ s.t. $p \succ q$. Consequently
$\neg \exists z \in E s.t. z \succ y$. Thus following definition $7$
$E$ is not a super-stable extension. Contradiction.



Assume now that $E$ is a conflict free set of arguments and for
all $E' \in 2^{\A}$ with $E' \rhd_T E$ there are $a_1, a_2 \in E'$
such that $(a_1, a_2) \in \C$. We prove that $E$ is a super-stable
extension. We show first that $E$ is a stable extension. Given
that $E$ is by definition conflict-free, it suffices to show that
for all
$a \not \in E$ there is $a' \in E$ s.t. $(a', a) \in \R$.\\
%
Assume that there is $a \not \in E$ s.t. for all $a' \in E$ it is
the case that $(a', a) \not  \in \R$ and  $(a, a') \not  \in \R$.
Then, since $E \cup \{a\} \supset E$, it holds that $E \cup \{a\}
\rhd_T E$. Moreover, $E \cup \{a\}$ is conflict-free,
contradiction. Therefore it must be the case that for all $a' \not
\in E$ there must be $a \in E$ such that $(a', a)  \in \R$ or $(a,
a') \in \R$.

Thus, in order to show that $E$ is a stable extension, it is
sufficient to prove that $\neg \exists a, b \in \A$, such that $a
\in E$, $b \not \in E$ and $(b,a) \in \R$ and there is no $c \in E$
with $(c,b) \in \R$. By way of contradiction assume that exists
$\alpha \not \in E$, and $b \in E$ s.t. $(\alpha, b) \in \R$ and
there is no $c \in E$ with $(c, \alpha) \in \R$. Then, define
$B(\alpha) = \{b | b \in E, \alpha \succ b, (\alpha, b) \in \C \}$
and $E' = (E \setminus B(\alpha)) \cup \{\alpha\}$.  First note that
$E'$ is by construction conflict free. We show that $E' \rhd_T E$.
Moreover, $E \setminus E' = B(\alpha)$, and $\alpha \succ b$ for all
$b \in B(\alpha)$. It remains to show that for all $a \in E'$ and $b
\in E$ with $a \not = b$ it holds that either $a \succeq b$ or $a
\not \succeq b$ and $b \not \succeq a$. Assume that this is not the
case, ie. exists pair $a' \in E'$, $a \in E$ with $a \not = a'$ and
$a \succ a'$.

By lemma we know....


\vspace*{2cm}

We now prove that $E$ is a super-stable extension.  Assume that it
is not the case. From definition 7 it follows that there exists $y
\not \in E, \exists x \in E$ s.t. $y \succ x$, $\neg \exists z \in
E$ s.t. $z \succ y$ and $\forall p, q$ s.t. $ q \in E, p \not \in E$
either $q \nsucc p$ or $\exists r \not \in E$ s.t. $r \succ q$.\\
Assume first that $(x, y) \in \C$. Then, ...\\
%
Assume now that $(x, y) \not \in \C$. Define $K=\{a | a \not \in E,
\exists b \in E$ s.t. $a \succ b$, and $\not \exists c \in E$ s.t.
$c \succ a$ $\}$, and let $M_K$ be a stable extension of the theory
induced by the set of arguments $K$. Clearly $K$ and $M$ are
non-empty. Let $K'$ be a stable extension of the theory induced by
the set of arguments $\A \setminus ( K \cup \Gamma^+(K))$ and define
$E'= K \cup K'$. {\bf This construction needs to be changed.} By
construction $E'$ is conflict free. We show that $E' \rhd_T E$.

\vspace*{1cm}


\end{proof}



A direct consequence of the definition \ref{dominance} and the
theorem \ref{rank-theo-neq} is the following proposition.

\begin{prop}\label{dom-super}
A super-stable extension dominates every stable extension under
the dominance relation $\rhd_T$.
\end{prop}

\begin{defi} \label{gd}
Let $T_D$ = $\dt$ be a \emph{decision theory} where $\paf$ is a
PBAT and $O$ is a set of options (or alternatives) each of which
is supported by the arguments of an element of the set $2^{\A}$.
We call then \emph{good decision} the choice of the options that
are supported by a super-stable extension.
\end{defi}

\begin{defi} \label{dom-opt}
Let $T_D$ = $\dt$ be a \emph{decision theory}, $o,o' \in O$ two
options and $E,E' \in 2^{\A}$ their respective supporting sets of
arguments. Then we say that $o$ \emph{dominates} $o'$ iff $E$
\emph{dominates} $E'$.
\end{defi}

A direct consequence of the definition \ref{gd}, \ref{dom-opt} and
the proposition \ref{dom-super} is the following property.

\begin{property}
The good decisions choose the dominating options
\end{property}

\begin{prop}\label{rank-trans-2}
 The $\rhd_T$ relation is transitive.
\end{prop}
%
\begin{proof}
We prove by case analysis that if $A_1, A_2, A_3 \subseteq \A$, with
$A_1 \rhd_T A_2$ and $A_2 \rhd_T A_3$, then $A_1 \rhd_T A_3$. To
prove $A_1 \rhd_T A_3$ we either show that $A_1 \supset A_3$, or \\
(p1) $\forall a \in A_1$, $\forall d \in A_3$ it holds that $a
    \succeq d$\\
(p2) $\forall d \in A_3 \setminus A_1$ $\exists a \in A_1$ s.t. $a
\succ d$


{\em Case 1}: Assume that $A_1 \supset A_2$ and $A_2 \supset A_3$.
Obviously $A_1 \supset A_3$ and therefore $A_1 \rhd_T A_3$. Also if
$A_1 \supset A_3$, $A_1 \rhd_T A_3$ follows immediately.

{\em Case 2}: Suppose that\\
(a1) $\forall a \in A_1$, $\forall b \in A_2$ it holds that $a
    \succeq b$\\
(a2) $\forall c \in A_2$, $\forall d \in A_3$ it holds that $c
    \succeq d$\\
(b1) $\forall b \in A_2 \setminus A_1$ $\exists a \in A_1$ s.t. $a
\succ b$\\
(b2) $\forall d \in A_3 \setminus A_2$ $\exists c \in A_2$ s.t. $c
\succ d$\\
(b3)  $A_1 \not \supset A_2$, $A_2 \not \supset A_3$,  $A_1 \not
\supset A_3$.


We first prove (p1) above. Let $a, d$ be a pair of arguments s.t. $a
\in A_1$, $ d \in A_3$. By (a1) we know that there exists $b \in
A_2$ s.t. $a \succeq b$. By (a2) we know that $b \succeq d$,
therefore $a
 \succeq d$.

We now prove (p2). Let $ d \in A_3 \setminus A_1$. First assume that
$ d \in A_2$. By (b1) we know that $\exists a \in A_1 $ s.t. $a
\succ d$. Now assume that $ d \not \in A_2$. Then $ d \in A_3
\setminus A_2$, and by (b2) $ \exists c \in A_2 $ s.t. $c \succ d$.
If $c \in A_1$ we are done. If $c \not \in A_1$ then $c \in A_2
\setminus A_1$, and by (b1) $ \exists a \in A_1$ s.t. $a \succ c$.
Therefore $a \succ d$.

{\em Case 3}: Suppose that\\
(a) $A_1 \supset A_2$\\
(a2) $\forall c \in A_2$, $\forall d \in A_3$ it holds that $c
    \succeq d$\\
(b2) $\forall d \in A_3 \setminus A_2$ $\exists c \in A_2$ s.t. $c
\succ d$\\
(b3) $A_2 \not \supset A_3$,  $A_1 \not \supset A_3$.

{\bf To be completed}

{\em Case 4}: Suppose that\\
(a) $A_2 \supset A_3$\\
(a2) $\forall a \in A_1$, $\forall b \in A_2$ it holds that $a
    \succeq b$\\
(b2) $\forall b \in A_2 \setminus A_1$ $\exists a \in A_1$ s.t. $a
\succ b$\\
(b3) $A_1 \not \supset A_2$,  $A_1 \not \supset A_3$.

{\bf To be completed}


\end{proof}


{\bf Here we discuss other methods for comparing sets of arguments
using the work on preferences over sets mentioned by Leila}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\fi


\section{A multi-criteria view of PBAT}

In the previous sections we investigated how standard
argumentation semantics can be extended to accommodate preference
information on the arguments. In this section we change our
perspective and explore a more direct link between argumentation
and decision theory. More specifically, we interpret arguments as
criteria and regard preferences as information on the relative
importance of these criteria. Under this perspective argumentation
can be understood as Multiple Criteria Decision Problem (MCDP). We
start our analysis with a definition of the problem that leaves
out some of its aspects  that are not directly relevant to our
purposes.



\begin{defi}
A {\em Multiple Criteria Decision Problem (MCDP)} is a triple $P=(A,
K, \succeq)$ where
%
%The basic elements of a MCDP are the following
\begin{itemize}
 \item $A=\{a_1, \ldots, a_n \}$ is the set of {\em attributes}.\\
 A set of values is associated with each attribute, denoted by $
 v(a_1), \ldots, v(a_n)$
%
 \item $K=\{\gg_{a_1}, \ldots,  \gg_{a_n}\}$ is the set of {\em criteria}.
 A criterion $\gg_{a_i}$ is a pre-order associated with the values of an
 attribute $a_i$ % ie. $\gg_{a_i} \subseteq v(a_i) \times v(a_i)$.
%
 \item
  $\succeq$ is pre-order on the criteria
%  ie., $\succeq \subseteq K  \times K$.

% A ranking $\succeq$ on the criteria,
%  %$K=\{ \gg_{a_1}, \ldots \gg_{a_n} \}$,
%  ie., $\succeq \subseteq K  \times K$.
\end{itemize}
%
An {\em alternative} $l$ wrt to a MCDP $P=(A, K, \succeq)$ is any $l
\in v(a_1) \times \ldots \times v(a_n)$. We denote the set of
alternatives by $L_P$.
\end{defi}

In certain situations, a {\em solution} to a MCDP is a ranking
relation $\unrhd$ on the set of alternatives $L$, ie. $\unrhd
\subset L \times L$. Usually a solution to a MCDP has to satisfy
certain properties \cite{TsoukiasBook}.

The following definition shows that argumentation can be transformed
in a meaningful way into a MCDP.


\begin{defi}
 Given a PBAT $T=\paf$, where $\A=\{a_1, \ldots, a_n\}$,
we define its corresponding MCDP $M_T=(A_T, K_T, \succeq_T)$ as
follows:
\begin{itemize}
 \item $A_T=\A$, with $v(a_i)=\{a_i^+, a_i^-\}$, for each $a_i \in
 A_T$.
%
 \item $K_T=\{\gg_{1}, \ldots, \gg_{n} \}$, where $\gg_i$, for $1 \leq i \leq n$,
 is defined as the preference $a_i^+ \gg_{i} a_i^-$.
%
\item $\succeq_T=\succeq$
\end{itemize}
\end{defi}

The following is an example of a translation of a specific PBAT
into a MCDP.

\begin{ex}
Consider the PBAT $T=\paf$, where $\A=\{a_1, a_2, a_3\}$, and the
underlying preference relation $\succeq$ defined as: $a_1 \succ
a_2$, $a_1 \succ a_3$, $a_2 \succeq a_3$, $a_3 \succeq a_2$. The
corresponding MCDP is defined as $M_T=(A_T, K_T, \succeq_T)$, where:
\begin{itemize}
 \item $A_T=\{a_1, a_2, a_3\}$, with $v(a_1)=\{a_1^+, a_1^-\}$,
 $v(a_2)=\{a_2^+, a_2^-\}$, $v(a_3)=\{a_3^+, a_3^-\}$.
 \item $K_T=\{\gg_{1}, \gg_{2}, \gg_{3} \}$, with
 $a_1^+ \gg_{1} a_1^-$, $a_2^+ \gg_{2} a_2^-$, $a_3^+ \gg_{3} a_3^-$.
\item $\succeq_T=\succeq$
\end{itemize}
\end{ex}

Several methods have been proposed in the literature, the
applicability of which in many cases depends on the features of
the MCDP at hand.
%
Among the methods for tackling MCDPs that appear in the literature
and are applicable to the case we consider, it seems that the
Regime method \cite{RegimeOrig} is the closest to the spirit of
the stable extensions semantics. Here we discuss a simplified
version of the method as it appears in \cite{RegimeSurv}.

The Regime method works as follows. For any two alternatives $A_i$,
$A_j$, let $K^+$ be the set of criteria according to which $A_i$ is
better than $A_j$, and $K^-$ be the set of criteria according to
which $A_j$ is better than $A_i$. Regime ranks $A_i$ better than
$A_j$, denoted by $A_i \rhd_R^t A_j$, if $K^+ \not = \emptyset$ and
there is an injective map from $K^-$ to $K^+$ by which each
criterion in $K^-$ is mapped to a more important criterion in $K^+$.
The set of optimal alternatives is then $\{ A_o: \forall i \neg (A_i
\rhd_R^t A_o) \}$.

We can easily define a preference order on the sets of arguments of
a PBAT that captures the Regime method. To do this we associate to
any set of arguments $A$, an alternative $A^t=\{a^+| a \in A\} \cup
\{a^-| a \not \in A\}$.

\begin{defi}\label{reg-def1}
Let $T=\paf$ be a PBAT and $M_T=(A_T, K_T, \succeq_T)$ its
corresponding  MCDP. For any $A_1, A_2 \subseteq  2^{\A}$, it
holds that $A_1 \rhd_R A_2$ if $A_1^t \rhd_R^t A_2^t$.
\end{defi}

We can now define the notion of a {\em regime extension} of a PBAT
by characterizing it in a way similar to the stable extensions.

\begin{defi}\label{reg-def2}
A set of arguments $E$ is a {\em regime extension} of a PBAT
$T=\paf$ if there are no arguments $a, b \in E$ s.t. $(a, b) \in
\C$, and for all $E' \in 2^{\A}$ such that $E' \rhd_R E$, there
are $a_1, a_2 \in E'$ such that $(a_1, a_2) \in \C$.
\end{defi}

We now apply the previous definition to the story of
\ref{counter-trans-ex}, and observe that it yields the correct
result.

\begin{ex}
Consider again the theory $T$ of example \ref{counter-trans-ex}.
The corresponding MCDP $M_T=(A_T, K_T, \succeq_T)$ can be defined
as outlined above. Consider the two sets of arguments $E_1 =\{a_1,
a_3 \}$ and $E_2 =\{ a_2, a_4 \}$ of $T$ which correspond to the
alternatives $E_1^t=\{a_1^+, a_2^-, a_3^+, a_4^- \}$ and
$E_2^t=\{a_1^-, a_2^+, a_3^-, a_4^+ \}$. For the comparison $E_2^t
\rhd_R^t E_1^t$ we have that $K^+=\{ a_2, a_4\}$, $K^-=\{a_1,
a_3\}$, and the mapping $a_1 \rightarrow a_2$, $a_3 \rightarrow
a_4$. For the comparison $E_1^t \rhd_R^t E_2^t$ we have that
$K^+=\{ a_1, a_3\}$ $K^-=\{a_2, a_4\}$, but there is no suitable
mapping. Therefore we conclude $E_2 \rhd_R E_1$. Moreover, $E_2$
is a regime extension of $T$.
\end{ex}

%The following result establishes a link between regime and stable
% extensions.
%
%\begin{thm}
%  A regime extension of a PBAT $T$ is also a stable
%  extension of $T$.
%\end{thm}
%
%\begin{proof}
%According to definition \ref{reg-def2} a set of arguments $E$ is a
%{\em regime extension} of a PBAT $T=\paf$ if there are no
%arguments $a, b \in E$ s.t. $(a, b) \in \C$, and for all $E' \in
%2^{\A}$ such that $E' \rhd_R E$, there are $a_1, a_2 \in E'$ such
%that $(a_1, a_2) \in \C$. From definition \ref{reg-def1} we know
%that for any $E, E' \subseteq 2^{\A}$, it holds that $E \rhd_R E'$
%if $E^t \rhd_R^t E'^t$ where $E^t=\{a^+| a \in E\} \cup \{a'^-| a'
%\not \in E\}$ and $E'^t=\{b^+| b \in E'\} \cup \{b'^-| b' \not \in
%E'\}$ are the associated alternatives and $a,a',b,b'$ are
%arguments. We also know that $E \rhd_R^t E'$ if $K^+ \not =
%\emptyset$ and there is an injective map from $K^-$ to $K^+$ by
%which each criterion in $K^-$ is mapped to a more important
%criterion in $K^+$ where $K^+$ be the set of criteria according to
%which $E$ is better than $E'$, and $K^-$ be the set of criteria
%according to which $E'$ is better than $E$. In other words, this
%means that for each argument that belongs to $E'$ there is a more
%important argument that belongs to $E$. Formally, this means that
%for all arguments $a,a'$ s.t. $a \in E \setminus E'$ and $a' \in
%E' \setminus E$ it holds that $a \succ a'$. From definition
%\ref{ECAI-def1} we have that $E \rhd E'$. From that, definition
%\ref{reg-def2} and Theorem \ref{rank-theo}, it follows that $E$ is
%a stable extension.
%\end{proof}



\section{Conclusion and Future Work}

In this paper we pointed out that Dung's stable extensions semantics
when applied in preference-based argumentation frameworks for
decision making purposes lead to counter-intuitive conclusions. A
similar problem was also identified by Horty in \cite{Horty01}. This
mainly holds for argumentation theories where the preference
relation used for defining the relative strength of individual
arguments contains incomparability. To resolve this problem we
proposed a new acceptability semantics called \textit{super-stable
extensions} which allows to capture the conclusions corresponding to
the good decisions and to avoid the counter intuitive ones which
could correspond to bad decisions. Moreover, we showed that
preference-based argumentation can be understood as a
multiple-criteria decision problem allowing to that way the
exploration of the application of theoretical results of the
decision theory in argumentation. Therefore, this work can been seen
as an attempt to bring new ideas from decision theory to
argumentation.

Our future work concerns the definition of a binary relation
$\rhd_{SS}$ on the sets of arguments of a PBAT that will be proved
exactly the preference relation that is induced by the
super-stable extensions semantics and to prove the correspondence
between both. This will be the equivalent result of the one we
proved in \cite{DiMoAm2008.1} between the preference $\rhd$ and
the stable extensions.

\paragraph{Acknowledgments.} We thank Alexis Tsoukias for many
fruitful discussions on several aspects of this work. We also thank
Michael Maher for his helpful comments.

%\bibliographystyle{elsarticle-num}
%\bibliographystyle{named}
\bibliographystyle{splncs}
\bibliography{Negotiation}

\end{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
