1 Introduction
The field of computational models of argumentation [1] aims at reflecting on how human argumentation utilizes incomplete and inconsistent knowledge to construct and analyze arguments about the conflicting options and opinions.
The most popularly used framework to talk about general issues of argumentation is that of abstract argumentation [2], which provides a unifying and powerful tool for the study of many formal systems developed for commonsense reasoning. In the past nearly 20 years, several different kinds of semantics for abstract argumentation system have been proposed that highlight various aspects of argumentation [3, 4, 5]. Those semantics partition the set of arguments into two classes: extensions and nonextensions. Each extension is a set of arguments, which is able to “survive together” and represents a coherent point of view. In order to reason with a semantics one has to take either a credulous or skeptical perspective. In other words, an argument is ultimately accepted with respect to a semantics if it belongs to every extension; an argument is rejected if it dose not belong to any extension; and an argument is undecided if it is in some extensions and not in others.
However, those semantics may exhibit a variety of problematic aspects such as emptiness, nonexistence, multiplicity [6] when encountering cycles, and are not suitable for practical applications in some scenarios. Considering an argument system whose grounded extension is empty, for example, if one must make a choice, then the grounded semantics is unavailable since all arguments are unacceptable in this case.
Recently, [7] introduces a new family of semantics, which provide a graded assessment to arguments, i.e., it ranks arguments from the most acceptable to the weakest one(s). In fact, this line of thinking has been mentioned in [8], in which two approaches, generic local valuation and global valuation, are proposed to evaluate the strength of an argument, and then a preordering (ranking) on arguments is induced by those strength values. In particular, the authors show that the approach for local valuation generalizes the categoriser function [9], and enables to handle cycles, then the strength valuation is the solution of seconddegree equations. However, there is no detail about the following questions: Does there exist a solution for these equations? If it exists, is it unique or multiple and how to find them?
In this paper, we expect to tackle these issues by fixedpoint technique. In addition, a rankingbased semantics, called categoriserbased ranking semantics, is defined in the light of categoriser valuation, and some of its properties are investigated. Lastly, we prove that the semantics satisfies some of the axioms, proposed by [7], which a rankingbased semantics should satisfy. The remainder of this paper is structured as follows. In Section 2, we briefly recall some backgrounds on abstract argumentation and the rankingbased semantics for argumentation frameworks. In Section 3, we employ the fixedpoint technique to analyze the categoriser strength valuation for argumentation system, and the categoriserbased ranking semantics is defined. We relate the semantic with [7] in Section 4 and conclude in Section 5.
2 Preliminaries
2.1 Abstract Argumentation Framework
Abstract argumentation frameworks [2] convey a very simple view on argumentation since they do not presuppose any internal structure of an argument. Here, the interactions among arguments are attack relations, which express conflicts between them.
Definition 1 (Abstract Argumentation Framework)
An argumentation framework is a pair where is a finite set of arguments and is a binary relation on , also called attack relation. means that attacks , or is a (direct) attacker of . Often, we write as .
We denote by (respectively, ) the subset of containing those arguments that attack (respectively, are attacked by) the argument , extending this notation in the natural way to sets of arguments, so that for , and .
A set is conflictfree iff . Let be the characteristic function of an argument system such that . We define the defenders of an argument , denoted by , are the attackers of the elements of . Formally, .
To define the solutions of an argument system, we mean selecting a set of arguments that satisfy some acceptable criteria. Let be conflictfree, then, is admissible iff ; is a preferred extension iff it is a maximal (w.r.t. ) admissible set; is a complete extension iff ; is a grounded extension iff it is the minimal (w.r.t. ) complete extension (or, alternatively, it is the least fixed point ; is a stable extension iff .
Example 1
Let us consider the abstract argumentation framework illustrated in Figure 1, in which vertices represent arguments and direct arcs correspond to attacks (i.e. elements of ). For this example, is the preferred, complete and grounded extension, however, there exist no stable extensions at all.
From the above example, it is shown that an abstract argumentation framework can be represented as a digraph, known as attack graph. One of the oftenused ways is to represent a digraph as 01 matrix for computational purposes. For an argumentation system with , we define the attack matrix of AF as the matrix such that if ; otherwise, .^{1}^{1}1In fact, the attack matrix of an argumentation framework is the transpose of the adjacency matrix of its corresponding attack graph. For instance, the attack matrix of the argument system in Example 1 is
Moreover, we denote the th row of by , which can indicate some information about the direct attackers of argument , e.g., the sum of shows the number of attackers of .
2.2 Rankingbased semantics for argument system
In order to provide a graded assessment to arguments, [7] proposes rankingbased semantics which rankorder the set of arguments from the most acceptable to the weakest one(s). This novel approach is distinct from the already existing semantics which assign an absolute status (accepted, rejected and undecided) for each argument. It compares pairs of arguments in the light of their respective sets of attackers, and states which arguments is more acceptable than another.
Before proceeding let us first formally characterize what we mean by the statements “ranking” in light of linear orderings [10].
Definition 2 (Ranking)
Let be some set. A ranking on is a binary relation on such that:

is total (i.e. for all , or );

is transitive (i.e. for all , if and , then ).
Let be the set of all rankings on .
In this paper, we give the meaning that is at least as acceptable as . This may be more intuitive than that of [7], in which the meaning of is just the opposite. Formally, if and only if and , which means and are equally acceptable. Moreover, , means is strictly more acceptable than , if and only if but not .
Definition 3 (Rankingbased Semantics)
Let be the set of all argument systems with finite argument set . A rankingbased semantics is a function .
In other words, for a given argumentation framework , the rankingbased semantics will transform into a ranking .
Generally, the ranking on arguments is induced by the strength values of the arguments. One of the most common approaches is categoriser function [9], which assigns a strength value to each argument. We will discuss it in the next section.
3 Argument ranking with categoriser function
3.1 Categoriser function for strength valuation
“Categoriser” function is originally used for “deductive” arguments, where an argument is structured as a pair , where is a set of formulae, called premise, is a formula, called claim, and entails . The attack relation considered here is canonical undercut and cycles are not allowed. The notion of an “argument tree” captures a precise and complete representation of attackers and defenders of a given argument, root of the tree. Then, categoriser function assigns a value to a tree of arguments. This value represents the relative strength of an argument (root of the tree) given all its attackers and defenders. The categoriser function, denoted by , is defined as
(1) 
Intuitively, the larger the number of defeaters of an argument, the lower its value. The larger the number of defenders of an argument, the larger its value.
Note that, in the work of [9], categoriser function solely handles acyclic graphs. However, Cayrol et al. reveal that the categoriser function is an instance of their generic local valuation [8], thus making it possible to cope with cycles. In this case, the strength values are the solution of nonlinear equations. Specifically, let be an argument system with , and its attack matrix be
, and suppose the strength values of all arguments be column vector
, of which the th component, denoted by or , represents the strength value of , then the strength values are the solution of the following equations:(2) 
Remark 1
3.2 Fixed point schema for categoriser equations
In [8], the authors show a simple example to evaluate arguments in a isolated cycle with categoriser valuation by solving second degree equations. For a complex argumentation system, however, no details are available about these questions: Do these equations always exist solutions in the reals and how many real solutions exist? If the real solutions exist, how should we find them? In this subsection, we will address these questions through fixedpoint techniques.
Firstly, let us transform the equations into the fixedpoint form [11]:
(3) 
where function maps into , and the function from to , called the coordinate function of , is defined by the categoriser function, i.e.,
(4) 
Intuitively, , where the bold (respectively, ) is an appropriately dimensioned column vector of all ’s (respectively ’s). Sometimes, we also write as the function of and , i.e.,
(5) 
Clearly, the function is a nonincreasing function with respect to and . Note that for any .
We convert the original problem into a fixed point problem. Then, finding the solutions of the categoriser equations is equivalent to finding the fixedpoints of . In other words, a fixedpoint of is a solution of (2). Now, let us give the following theorem, which shows that the solution of categoriser equations always exists.
Theorem 3.1 (Existence of categoriser valuation)
For any argumentation framework with , the categoriser valuation defined in (2) has at least one solution in .
Proof (Sketch)
We prove the equivalence result that function has at least one fixed point. The proof uses Brouwer’s fixed point theorem [12, Thm 2.14, pp. 24] and the observation that is homeomorphic to a closed ball (closed, bounded, connected and without holes) and function is continuous on it. ∎
The previous theorem is of utmost importance if we are to widely use categoriser valuation, since one would be turned away from an argumentation system that is not capable of assigning meaningful strength values (real solution) to arguments in all case.
Next we focus on the existence of a unique valuation. Assigning multiple solutions to an argumentation framework may be more interesting from a theoretical perspective, but we look forward to the kind of users of this framework to expect a unique valuation. One intuitive application of a unique categoriser valuation is that it may help removing ambiguity on argument ranking. We will show that for every argumentation system there always exists a unique categoriser valuation, and the valuation can be calculated by fixed point iteration.
Theorem 3.2 (Uniqueness of categoriser valuation)
Let be an argument system with . Then, the categoriser equations defined in (2) has a unique solution , which is the limit of the sequence of , defined from an arbitrarily selected in and generated by
(6) 
Proof
Let , and for each . Then, we can easily know that
(7) 
and that there exists such that
(8) 
Since is nonincreasing (i.e., for any , if then ), by applying on (7) and by induction, it is easy to see that
(9) 
On the other hand, from (8) and (9), we find for each . Letting , then and . In the following, we prove that .
Note that for all , then there exists and a continuous function such that
(10) 
Then, by (9), (10) and the nonincreasing property of , we have
(11) 
which implies that . So,
(12) 
As , thus by (12) we have
(13) 
Therefore, by (9) we get, for any integer
(14) 
Since is normal, both and are convergence sequences. By (13) and (14), thus, there exists such that
(15) 
Hence and . Letting and combining with (15), it follows , i.e., is a fixed point of .
Now, for any and for any , by induction, we have and . Then as . In particular, let , where is any fixed point of in , then for all , and we get . So, has a unique fixed point in . ∎
The proof of this theorem mainly refers to [13, Lmm 2.1]. An approximate calculation of the unique categoriser valuation is done by using Algorithm 1. In this paper, we set the initial strength values since we assume that each argument is not attacked at the beginning and has the maximum strength value . The iteration terminates when the change of the sequence is under a given tolerance
. As the proof of uniqueness suggests, the estimation of convergence rate of this algorithm is
(16) 
Remark 3
In Algorithm 1, we can see that at each iterative step the strength value of any argument is simultaneously recomputed in the light of its direct attackers (represented by ) and the strength values in the previous step (i.e., ). This exactly embodies the idea of “local approach” (i.e., the value of an argument only depends on the values of its direct attackers) in [8].
3.3 Categoriserbased ranking semantics
Now, we have shown that for the categoriser equations there always exists a unique solution for any argumentation framework. The solution assigns a numerical value to each argument, which can be interpreted as the strength of the argument. The greater the strength value, the more acceptable the argument. Thus, we can induce a ranking on arguments from the unique solution.
Definition 4 (Categoriserbased ranking semantics)
Let be an argumentation framework, and be the unique solution of (2). The categoriserbased ranking semantics is a rankingbased semantic and transforms into the ranking such that , if and only if .
Obviously, the categoriserbased ranking semantics satisfies that for any , if ; else , i.e., nonattacked arguments are more acceptable than attacked ones. Nonattacked arguments are supported by extensionbased semantics. They are part of any extension under complete, preferred, stable and grounded semantics. Therefore, it is naturel to believe that an argument which has no attackers is ranked higher than another argument which has attackers.
In addition, we give other properties of the categoriserbased ranking semantics:
Proposition 1
Let . The categoriserbased ranking semantics satisfies:

If , then .

If , then .
Proof
This proposition states that two arguments with the same direct attackers have the same ranking, and an argument, whose direct attackers pertain to the set of direct attackers of another argument, is at least as more acceptable than the argument.
Let us show an example of how the semantics works:
Example 2
Consider again the argument system in Fig. 1. Let and . Then, the valuation sequence , calculated by Algorithm 1, is shown in Fig. 2.
When , all arguments have the maximum strength value as we presuppose each argument is not attacked at the beginning.
When , then the strength value of each argument merely depends on the number of its direct attackers since the strength values of all argument from the previous step are . Thus, has the maximum strength value since it has no attacker, followed by with one attacker, and followed by and with two attackers, and followed by with three. From another perspective, since , then by Proposition 1 we have .
When , after a new round of calculation, the strength value of each argument is recomputed. But, since always holds, the ranking among them will not be changed. Note that the ranking on and is altered as the sum of the strength values of the attackers of is greater than that of .
……
After finitely many iterations, the valuation sequence gradually tends to be stable and converge to an approximative solution within a tolerable range. Actually, the valuation sequence reflects how argument strength values change with iterations. Note that has a maximum strength value , since it is not attacked, and all other arguments have the strength values less than since they are attacked by at least one argument. With the solution , the categoriserbased ranking semantics gives: .
4 Relating with ranking axioms
In [7], the authors set up a set of axiom (postulates) that rankingbased semantics should satisfy. In this section, we will formally show that the categoriserbased ranking semantics meets some of these postulates.
The first axiom is that a ranking on a set of arguments does not rely on their identity but only on the attack relations among them. In other words, if two argumentation system are isomorphic then they should have the same ranking semantics. The isomorphisms between argumentation frameworks and is a bijective function : such that for all , if and only if . Now we define the first axiom, called abstraction, as follows:
Axiom 1 (Abstraction (Ab))
A rankingbased semantics satisfies abstraction iff for any two argumentation framework and , for any isomorphism from to , we have , iff .
The second axiom states the question that whether an argument is at least as acceptable as an argument should be independent of any argument that is not connected to or , i.e., there is no path from or to (neglecting the direction of the edges). Let be the set of weakly connected components of AF. Each weakly connected component of AF is a maximal subgraph of AF in which any two arguments are mutually connected by a path (neglecting the direction of the edges).
Axiom 2 (Independence (In))
A rankedbased semantics satisfies independence iff for any AF and for any , , iff .
The third axiom, called void precedence, encodes the idea that nonattacked arguments are more acceptable than attacked ones.
Axiom 3 (Void Precedence (Vp))
A rankedbased semantics meets void precedence iff for any , , if and then .
The fourth axiom states that having attacked attackers is more acceptable than nonattacked attackers, i.e., being defended is better than not.
Axiom 4 (Defense precedence (Dp))
A rankedbased semantics satisfies defense precedence iff for every , , if , and then .
The next axiom says that an argument should be at least as acceptable as argument , when the direct attackers of are at least as numerous and wellranked as those of . This involves the concept of group comparison: Let be a ranking on a set of arguments . For any , iff there exists an injective mapping from to such that , . Moreover, is a strict group comparison iff (1) ; (2) or , .
Axiom 5 (CounterTransitivity (Ct))
A rankedbased semantics satisfies countertransitivity iff for every , , if then .
Axiom 6 (Strict CounterTransitivity (Sct))
A rankedbased semantics satisfies strict (CT) iff for any , , if then .
The following two axioms represent two opinions: give precedence to cardinality over quality (i.e. two weakened attackers is worse for the target than one strong attacker), or vice versa. In some situations, both choices are reasonable.
Axiom 7 (Cardinality Precedence (Cp))
A rankedbased semantics satisfies cardinality precedence iff for arbitrary argumentation framework , , if then .
Axiom 8 (Quality Precedence (Qp))
A rankedbased semantics satisfies quality precedence iff for arbitrary argumentation framework , , if such that , , then .
The last axiom focuses on the way arguments are defended. The main idea is that an argument which is defended against more attackers is more acceptable than an argument which is defended against a smaller number of attacks. There are two types of defense: simple and distributed. The defense of an argument is simple iff each defender of attacks exactly one attacker of , formally, such that . The defense of an argument is distributed iff every attacker of is attacked by at least one argument, i.e., such that .
Axiom 9 (DistributedDefense Precedence (Ddp))
A rankedbased semantics satisfies distributeddefense precedence iff for any , such that and , if the defense of is simple and distributed and the defense of is simple but not distributed then .
In addition, [7] provides some relationships between these axioms: if a rankingbased semantics satisfies (SCT) then it satisfies (VP); if satisfies both (CT) and (SCT), then it satisfies (DP); can not satisfy both (CP) and (QP). Now, we show which axioms are or are not compatible with the categoriserbased ranking semantics.
Theorem 4.1
The categoriserbased ranking semantics satisfies (Ab), (In), (VP), (DP), (CT) and (SCT), and does not satisfy (CP), (QP) and (DDP).
From the definition of the categoriser function, it can be easily seen that categoriserbased ranking semantics satisfies (Ab) and (In). To some extent, Proposition 1 is a special case of (CT). In particular, when then the semantics gives , which is a special case of (SCT). The (VP) and (DP) can be implied from (CT) and (SCT). Now, let us give a counter example to show that the semantics does not satisfy (CP) and (QP):
Example 3
Consider the argument system in Fig. 3, in which and . Clearly, . However, the categoriserbased ranking semantics gives (since and ), which conflicts with (CP). Note that for all (since and ). From (QP), should hold, but it is not true for the semantics.
The main reason of the counter situation in the above example is that these two axioms represent two extreme: one treats all attackers equally, and one merely focuses on some attacker (with highest rank with respect to the set of attackers of the argument) of an argument. In categoriser valuation, however, the value of an argument (represented by ) depends on both the number and quality (i.e., the strength values) of its attackers, the attackers of its attackers, etc.
Another reason that (CP) is not satisfied by the categoriser valuation is that (CP) concentrates too much on quite local topological aspects of an argumentation framework, but ignores the global topology [14]. However, the categoriser valuation is a global approach since the strength value of an argument depends on the strength values of its attackers, which is a recursive definition. For the same reason, the categoriserbased ranking semantics does not satisfy (DDP).
5 Conclusion
In this paper, we firstly investigated the existence and uniqueness of the categoriser strength valuation via fixedpoint technique. On this basis, we then defined a new rankingbased semantics, called categoriserbased ranking semantics, for abstract argumentation framework. We analyzed some general properties of the semantics, and prove that it satisfies some of the postulates that a rankingbased semantics should satisfy. Our ongoing work is about a deeper analysis of the approach and its relationships to other approaches.
References

[1]
Rahwan, I., Simari, G.R.:
Argumentation in artificial intelligence.
Springer (2009) 
[2]
Dung, P.M.:
On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and nperson games.
Journal of Artificial Intelligence 77(2) (September 1995) 321–357  [3] Baroni, P., Giacomin, M., Guida, G.: SCCrecursiveness: a general schema for argumentation semantics. Artificial Intelligence 168(1) (2005) 162–210
 [4] Dung, P.M., Mancarella, P., Toni, F.: A dialectic procedure for sceptical, assumptionbased argumentation. COMMA 144 (2006) 145–156
 [5] Baroni, P., Cerutti, F., Giacomin, M., Simari, G.R.: Computational Models of Argument. Volume 216. Ios Press (2010)
 [6] BenchCapon, T.J., Dunne, P.E.: Argumentation in artificial intelligence. Artificial intelligence 171(10) (2007) 619–641
 [7] Amgoud, L., BenNaim, J.: Rankingbased semantics for argumentation frameworks. In: Scalable Uncertainty Management. Springer (2013) 134–147
 [8] Cayrol, C., LagasquieSchiex, M.C.: Graduality in argumentation. J. Artif. Intell. Res.(JAIR) 23 (2005) 245–297
 [9] Besnard, P., Hunter, A.: A logicbased theory of deductive arguments. Artificial Intelligence 128(1) (2001) 203–235
 [10] Altman, A., Tennenholtz, M.: Axiomatic foundations for ranking systems. J. Artif. Intell. Res.(JAIR) 31 (2008) 473–495
 [11] Burden, R.L., Faires, J.D.: Numerical analysis. 2001. Brooks/Cole, USA
 [12] Teschl, G.: Nonlinear functional analysis. Lecture notes in Math, Vienna Univ., Austria (2001)
 [13] Li, K., Liang, J., Xiao, T.J.: Positive fixed points for nonlinear operators. Computers & Mathematics with Applications 50(10) (2005) 1569–1578
 [14] Thimm, M., KernIsberner, G.: Stratified labelings for abstract argumentation. arXiv preprint arXiv:1308.0807 (2013)
Comments
There are no comments yet.