Jonathan Ben-Naim
email: bennaim@irit.fr

Dov Gabbay
email: dov.gabbay@kcl.ac.uk

Preliminary Results on Reputation Systems: Favoring More Balanced Profiles ⋆

Keywords: reputation, ranking, axiomatization, multi-agent systems

In many large multi-agent systems (for example e-commerce applications), the users have to choose the agents to interact with. But this choice is difficult, in particular because the agents are too numerous. For the same reason, it is impossible to call a trusted arbiter that can judge every one of them. However, the agents provide a lot of information about their peers (for example feedbacks from past transactions). Consequently, the goal is to construct from this information an object helping the users to make decisions about the agents. Many reputation systems have been developed to achieve this goal. In the present sketch, we develop and begin to analyze, from an axiomatic point of view, new systems favoring those agents that have a more balanced profile. More precisely, the information available about the agents is modeled by a support graph, that is, the nodes represent the agents and an arrow means that the source agent supports the importance of the destination agent. The object constructed from this information is a ranking of the agents showing the relative importance of each agent. Our ranking methods are based on the following principle: for an agent, to reach a certain position in the ranking, it is necessary to pass a certain threshold both in the quantity of supporters and in their quality.

Introduction

In many large multi-agent systems, the users have decisions to make about the agents. In particular, a user has to choose those to interact with. But this choice is difficult, particularly because the agents are too numerous. For the same reason, it is impossible to call a trusted arbiter that can judge every one of them.

However, the agents provide a lot of information about their peers. So, the goal is to construct, on the basis of this information, an object helping the users to make decisions. Many reputation systems have been developed to achieve this goal. They are called so because the object constructed typically gives a good account of the reputation of the agents.

Let us mention some important applications where a reputation system is needed. First of all, there are e-commerce applications, like Ebay. The agents are the buyers and the sellers and the information available about them takes the form of feedbacks from past transactions. Next, there are the webpages and their hypertext links. Indeed, a page can be seen as an agent and a link as the fact that the source page supports the importance of the destination page. Next, there are papers and their citations. Again, a paper can be seen as an agent and a citation as a positive opinion. As a last example, let us mention the bindings entity-key and the public key certificates. A binding E, K can be seen as an agent and a certificate written by E, signed with K, and supporting the validity of a binding E ′ , K ′ can be seen as a positive opinion of E, K on E ′ , K ′ .

The present sketch contains work in progress. It is designed for a workshop intended primarily as a forum for interaction and discussion. Consequently, it is largely incomplete in several aspects, in particular bibliography, formal definitions, and results. Concerning the contributions, we develop two new reputation systems based on the following principle: those agents that have a more balanced profile are preferred. To properly introduce this principle, we need to specify what we mean by the terms reputation system and what particular kind of such systems we investigate.

By reputation system, we mean a system composed of two parts. The first part is an environment containing many agents that have the possibility of providing information about their peers. The second part is a method that, in any possible situation, constructs from this information an object helping the users to make decisions about the agents.

In the present work, the information available about the agents is modeled by a support graph. A node represents an agent and an arrow means that the source agent supports the importance of the destination agent. The object constructed from such a graph is a ranking of the agents showing the relative importance of each agent. By ranking, we mean a reflexive, transitive, and total binary relation where a b means that a is at least as important as b. The rank of an agent can be seen as a good representation of its reputation, since it is determined by what is said about that agent. Although this framework is very simple, it is sufficient to provide solutions for all the aforementioned applications.

When comparing two agents, we consider two criteria: the number of supporters and their importance. Our ranking methods are based on the following principle: the agents that receive a more balanced kind of support are preferred. In other words, we want to prevent the agents that have a big flaw in some criterion from getting a high position in the ranking. More precisely, for an agent, to reach a certain position in the ranking, it is necessary to pass a certain thresh-old both in the quantity of supporters and in their quality. We call this the more-balanced-support principle.

We develop two completely different methods that follow this principle. One is based on refinements, the other on improvements. But actually, we strongly believe that both methods always give the same ranking, that is, we believe that they are two different ways to define the same ranking function. If this is indeed the case, this would indicate that the ranking function in question is relatively central, because it would be motivated from two completely different points of view.

Next, it is crucial to analyze ranking methods from an axiomatic point of view. To our knowledge, the first axiomatic study of such methods was started in a paper of M. Tennenholtz [START_REF] Tennenholtz | Reputation Systems: An Axiomatic Approach[END_REF] and further developed in several papers written in collaboration with A. Altman, in particular [START_REF] Altman | On the Axiomatic Foundations of Ranking Systems[END_REF], [START_REF] Altman | Quantifying Incentive Compatibility of Ranking Systems[END_REF], [START_REF] Altman | An Axiomatic Approach to Personalized Ranking Systems[END_REF], [START_REF] Altman | Incentive Compatible Ranking Systems[END_REF], and [START_REF] Altman | Axiomatic Foundations for Ranking Systems[END_REF]. In the present sketch, we begin to analyze our methods. More precisely, we present two axioms that are among the most important for the kind of ranking methods considered: transitivity and strict transitivity. We are very confident that both of our methods satisfy these axioms, which would provide theoretical justifications for them.

Axioms

Recall that a support graph is a graph where a node represents an agent and an arrow means that the source agent supports the importance of the destination agent. In addition, recall that a ranking method is a function that transforms any support graph into a ranking of the agents showing the relative importance of each agent. We present two important properties for the kind of ranking methods considered. Actually, they could be seen as two parts of one property, but to improve readability, we present them separately:

• Transitivity. Consider two agents a and b, and suppose that the group A of all supporters of a is at least as important as the group B of all supporters of b, then a should be ranked at least as high as b. We consider that A is at least as important as B iff B = ∅ or there exists an injective function f from B to A such that for each element x of B, f (x) is ranked at least as high as x.

• Strict transitivity. If the group A supporting a is strictly more important than the group B supporting b, then a should be ranked strictly higher than b. We consider that A is strictly more important than B iff (0) or (1) holds, where (0) is the following: A = ∅ and B = ∅, and (1) is that there exists an injective function f from B to A such that, first, for each element x of B, f (x) is ranked at least as high as x, and second, |B| < |A| or there exists x in B such that f (x) is ranked strictly higher than x.

These axioms are discussed in detail in [START_REF] Altman | Axiomatic Foundations for Ranking Systems[END_REF]. There exist several other desirable properties, but in the framework of this preliminary work, we investigate only those two.

A refinement-based ranking method

We develop a first ranking method based on the more-balanced-support principle. Note that a ranking on a set can be seen as an ordered partition of this set. By category, we mean an element of this partition. The idea is to begin with the trivial ranking R 0 that puts every agent in the same category, then we refine R 0 an infinite number of times, which gives R 1 , R 2 , etc. A final ranking is derived as follows: an agent is at least as important as another one iff this is the case in all the preliminary rankings.

In each refinement step, a new, finer, view on the quality of the agents becomes accessible. Our goal is to refine in such a way that, in the end, the following holds: for an agent, to reach a certain position in the final ranking, it is necessary to pass a certain threshold in every criterion. By criterion, we mean the quantity of supporters or any view on their quality.

Let us take a closer look at the first refinement step. When comparing two agents, a certain number of factors are considered: the quantity of supporters and every view on their quality. The influence of each factor is represented by a certain number of points. Concerning quantity, an agent naturally scores 1 point for each of its supporters. On the other hand, concerning the views on quality, no point can yet be scored. Indeed, in the first refinement step, these views are not yet accessible. They are precisely under construction. Therefore, they cannot have any influence on the first refinement.

So, each agent gets a certain score determined only by the quantity of supporters. If we were to refine R 0 on the basis of these scores, we would put in the top category those agents that have a maximal number of supporters, regardless of their importance. This does not correspond to our guideline. To counterbalance the absence of influence of quality, we limit the influence of quantity. More precisely, we cap the number of supporters considered in this step at 1, the minimal value such that the quantity of supporters still has some influence.

To summarize, if an agent has at least 1 supporter, it scores 1 point, and that is all. In other words, in the first refinement step, we consider two levels of quality: the level corresponding to a score of 0 and the level corresponding to a score of 1. The agents are evaluated on the basis of these two levels and ranked accordingly. The resulting ranking is called R 1 .

Next, we enter the second refinement step. Thanks to the scores obtained in the first step, we have now access to a first, rough, view on the quality of the agents. More precisely, we can distinguish between a basic and a non-basic agent. By basic agent, we mean an agent having no supporter. But, we cannot yet distinguish between two non-basic agents of different importance. This first view on quality will influence the second refinement.

More precisely, if a supporter becomes more important in the first view on quality, then the agent supported naturally scores 1 point. By becoming more important in the first view, we mean getting a score of 1 in the first refinement step. In parallel, we lift a bit the limitation on the quantity of supporters, so this factor keeps having some minimal influence. More precisely, we increase the cap on the number of supporters considered by 1. In other words, if an agent has at least 2 supporters, it scores an additional point.

So, each agent gets a score determined by the quantity of supporters and the first view on their quality. If we were to refine R 1 on the basis these scores, we would put in the top category the agents having a maximal number of supporters that are important in the first view on quality, regardless of their importance in the next, finer, views that will become accessible later. This does not correspond to our guideline. Consequently, we limit the influence of the first view.

More precisely, the advancement of only one supporter is taken into account at a time. Therefore, we have to choose the order in which the supporters will be treated. We adopt the following strategy: the more a supporter is important, the earlier its advancement will be taken into account. More precisely, we introduce some linear ordering l(R 1 ) on the agents that agrees with R 1 . The choice of this linear ordering has no effect on the result. In the second refinement step, only the advancement of the best supporter of a in l(R 1 ) will possibly allow a to score a point. In the next step, we will take into account the advancement of the second best supporter, and so on.

To summarize, if an agent a has at least 2 supporters, it scores 1 point. If the best supporter of a in l(R 1 ) exists and gets a score of 1 in the first step, then a scores 1 point. In other words, for each category of R 1 , three levels of quality are considered: the levels corresponding respectively to a score of 0, 1, and 2. The agents are evaluated on the basis of these three levels and ranked accordingly inside each category of R 1 . The resulting ranking is called R 2 .

Next, we enter the third refinement step. Thanks to the scores obtained in the second step, we have now access to a second, finer, view on the quality of the agents. This second view will influence the third refinement. More precisely, if a supporter becomes more important in this second view, then the agent supported scores a certain number of points. In addition, the more a supporter becomes important, the more the agent supported scores many points. More precisely, if a supporter makes x advances in the second view on quality, then the agent supported scores x points. By making x advances in the second view, we mean getting a score of x in the second refinement step. As previously, we limit the influence of this second view on the current refinement. In parallel, we lift a bit the limitations on the two other factors: the quantity of supporters and the first view on their quality.

To summarize, if an agent a has at least 3 supporters, it scores 1 point. If the second best supporter of a in l(R 1 ) exists and gets a score of 1 in the first step, then a scores 1 point. If the best supporter of a in l(R 2 ) exists and gets a score of x in the second step, then a scores x points. So, for each category of R 2 a certain number of levels of quality are considered, one for each possible score. The agents are evaluated on the basis of these levels, and ranked accordingly inside each category of R 2 . The resulting ranking is called R 3 . And so on.

More generally, in each refinement step, we have access to a new, finer, view on the quality of the agents. When a new view becomes accessible, we limit its influence on the current refinement. We do it in order to give time to the next, finer, views to become accessible and to influence significantly the final ranking. In parallel, we lift a bit the limitations on the quantity of supporters and on the already accessible views on their quality, so these factors keep having some minimal influence. As a result, for each agent and for each position in the ranking, the following holds: for that agent to reach that position, it is necessary to pass a certain threshold in the quantity of supporters and in every view on their quality, which corresponds to our guideline.

Here is for example a support graph containing 9 agents, and below are the five first rankings obtained from it by the refinement-based method:

Example 1.

The initial ranking, denoted by R 0 , puts every agent in the same category. We enter the first refinement step. The agents a 0 and a 1 have no supporter, so they get a score of 0. Actually, if an agent gets a score of 0 in some step, it will get a score of 0 in all the subsequent steps. The other agents do have supporters, so they all get a score of 1. These scores represent a first, rough, view on the quality of the agents. The resulting ranking is denoted by R 1 .

We enter the second refinement step. The agent a 3 gets a score of 0. The agents a 2 , a 4 , a 6 , and b 1 get a score of 1. More precisely, a 2 scores 1 point because it has 2 supporters. Concerning a 4 , a 6 , and b 1 , they score 1 point because they have a supporter that makes an advance in the first view on the quality of the agents. The agents a 5 and b 0 both get a score of 2. Indeed, they score 1 point because they have two supporters and an additional point because they have a supporter that makes an advance in the first view on quality. These scores represent a second, finer, view on the quality of the agents. The resulting ranking is denoted by R 2 .

We enter the third refinement step. The agents a 2 , a 4 , and a 5 get a score of 0. The agent b 0 gets a score of 1, because it has a supporter that makes an advance in the second view on quality. The agents a 6 and b 1 both get a score of 2, because they have a supporter that makes 2 advances in the second view on quality. These scores represent a third, finer, view on quality. We denote by R 3 the resulting ranking.

We enter the fourth step. The agent a 6 gets a score of 0. The agent b 1 gets a score of 1, because it has a supporter that makes an advance in the third view on quality. The agent b 0 gets a score of 2, because it has a supporter that makes 2 advances in the third view. The resulting ranking is denoted by R 4 .

All the subsequent refinements leave R 4 unchanged, so R 4 is the final ranking obtained in this example by our refinement-based method.

An improvement-based ranking method

We develop a second, completely different, ranking method based on the morebalanced-support principle. Suppose a support graph is given. The idea is to imagine that the support links generate, step by step, two kinds of improvements: improvements in the importance of an agent and improvements in the importance of an improvement generated earlier. More precisely, we construct step by step from the support graph, an improvement graph where a node represents either an agent or an improvement, and an arrow means that the source element is an improvement in the importance of the destination element.

Initially, the improvement graph contains only a certain number of nodes, no link. These nodes represent exactly the same agents as those of the support graph. Next, for each agent a and each agent b, if a supports b, we introduce a new node p representing an improvement, and an arrow from p to b meaning that p is an improvement in the importance of b. In other words, the support a provides to b generates an improvement in the importance of b.

In the second step, for each agent a and each improvement p introduced in the first step, if a supports the agent (providing the support) that generated p, then we introduce a new improvement p ′ and an arrow from p ′ to p. In other words, the support a provides to an agent b generates an improvement in the importance of every improvement generated by b.

More generally, in the i th step, for each agent a and each improvement p introduced in the (i -1) th step, if a supports the agent that generated p, then we introduce a new improvement p ′ and an arrow from p ′ to p.

In some sense, we unfold the support graph, that is, we replace a graph possibly containing cycles by a graph with no cycle, but possibly containing infinite chains.

Here is for example the improvement graph obtained from the support graph presented in Example 1:

Example 2.
For each agent a, we extract from the improvement graph, the subgraph S(a) of all improvements related (directly or indirectly) to a. This subgraph is called the improvement structure of a. The crucial point is that the form of S(a) gives a good idea what kind of support a receives. More precisely, the more S(a) is horizontally large, the more the supporters of a are numerous. The more it is vertically large, the more they are important. So, the idea is to rank the agents on the basis of the form of their improvement structures. More precisely, suppose we have at our disposal a ranking of the improvement structures showing the relative quality of the form of each structure. Then, we define that an agent a is at least as important as an agent b iff S(a) is ranked at least as high as S(b).

So, it remains to construct a ranking of the improvement structures. In accordance with the more-balanced-support principle, we favor those structures that have a more balanced form. In other words, for a structure, to reach a certain position in the ranking, it is necessary to pass a certain threshold both in the horizontal and in the vertical development. To meet this requirement, we adopt the following strategy: the rank of an improvement structure is determined by the rate at which it can be constructed under certain limitations. Let us explain this strategy.

A construction of an improvement structure S(a) is a step-by-step development that begins with a and ends with S(a), or is more and more approaching S(a). In each step, two restrictions are imposed on the development of the structure under construction. First, only improvements that are directly connected to the existing elements can be added. In other words, it is impossible to add (in one step) a chain of improvements. This limits the vertical development. The second restriction is the following: for each existing element, at most one new improvement can be introduced and attached to it. This limits the horizontal development.

In more precise terms, a construction of S(a) is an infinite sequence of graphs S 0 , S 1 , . . . such that the three following points hold: first, S 0 consists only of a; second, the union of all S i 's is identical to S(a); and third, S i+1 can be obtained from S i by introducing, for each node p of S i , at most one new node p ′ and a link from p ′ to p.

For example, consider the improvement graph given in Example 2. Here is a construction of S(a 6 ):

Example 3.
Intuitively, because of the development restrictions, the following holds: for an improvement structure, to be constructible at a certain rate, it is necessary to be sufficiently developed both horizontally and vertically. In other words, it is necessary to be sufficiently balanced. So, we rank the improvement structures on the basis of the rate of their constructions. More precisely, suppose we have at our disposal a ranking of the constructions showing the relative intensity of the rate of each construction. Then, we define that the form of a structure S is at least as good as the form of a structure S ′ iff some construction of S is ranked at least as high as every construction of S ′ . So, the last step is to construct a ranking of the constructions. A construction S 0 , S 1 , . . . defines a certain sequence of increases, that is, the sequence n 0 , n 1 , . . . such that every n i is equal to the number of new elements introduced in S i . For example, the sequence of increases defined by the construction of S(a 6 ) given in Example 3 is 1, 1, 1, 2, 0, 0, . . . . We consider that the rate of a construction S 0 , S 1 , . . . is at least as high as the rate of a construction S ′ 0 , S ′ 1 , . . . iff both constructions define the same sequence of increases, or S 0 , S 1 , . . . defines a lexicographically greater sequence, that is, in some step i, more improvements are introduced in S i than in S ′ i , and in every previous step j, the same number of improvements are introduced in S j and S ′ j . To summarize, we define a ranking showing the relative intensity of the rate of each construction, from which we define a ranking showing the relative quality of the form of each improvement structure, from which we finally define a ranking showing the relative importance of each agent. Put differently, an agent a is at least as important as an agent b iff there exists a construction of S(a) such that the rate of this construction is at least as high as the rate of every construction of S(b).

For example, consider the support graph introduced in Example 1. For every agent a, we have chosen one of the highest-ranked construction of S(a), and we have displayed below the sequence of increases defined by this construction. Finally, the ranking of the agents obtained from the support graph of Example 1 by the improvement-based method is also displayed below. It is identical to the one obtained by the refinement-based method.

Example 4.

To conclude, we have developed two new ranking methods based on the following principle: for an agent, to reach a certain position in the ranking, it is necessary to pass a certain threshold both in the quantity of supporters and in their quality. We are very confident that both of our methods satisfy transitivity and strict transitivity, which would provide theoretical justifications for them. In addition, we strongly believe that these two methods are actually two different ways to define the same ranking function. If this is the case, this would mean that the ranking function in question is relatively central, because it would be motivated from two completely different points of view. We are working on these conjectures and on a complete axiomatization of our ranking methods.

The first author is supported by the French ANR-06-SETI-006 project "ForTrust".


Jonathan Ben-Naim

Emil Weydert

On Agent Prioritization in Trust Networks *

In multi-agent communities, the subjective attitudes of agents towards other agents are of central importance. If the agents report these attitudes, then an external observer may use this possibly partial social assessment to estimate in particular the trustability of the agents. We present a simple framework to specify procedures for deriving agent prioritizations from binary support relations among agents. We propose a number of rationality postulates, describe two specific approaches, and investigate to what extent they satisfy these principles.

Introduction

In multi-agent communities, the subjective attitudes of agents towards other agents are of central importance. If the agents report these attitudes, then an external observer may use this usually partial social assessment to estimate some corresponding objective qualities of the agents. In particular, one can exploit the positive feedback on agents to evaluate their actual reliability or trustability. This may be done by taking into account not only the immediate neighbours, but the whole backyard, if not the entire network, even including disconnected parts (in the most general approaches).

Several methods for estimating trust have been proposed in the literature. Most of them are numerical, for instance, the Bayesian reputation systems, e.g. [START_REF] Jøsang | The Beta Reputation System[END_REF][START_REF] Withby | Filtering Out Unfair Ratings in Bayesian Reputation Systems[END_REF]. They take binary ratings (either positive or negative) as their input and derive from them a reputation score represented by a beta probability density function, possibly accompanied by a confidence parameter.

Another example is based on the belief model in [START_REF] Jøsang | Trust-Based Decision Making for Electronic Transactions[END_REF][START_REF] Jøsang | A Logic for Uncertain Probabilities[END_REF], which defines an opinion as a tuple (b, d, u, a) where b represents belief, d disbelief, u uncertainty, and a the base rate probability in the absence of evidence. Then Subjective Logic [START_REF] Jøsang | A Logic for Uncertain Probabilities[END_REF] is used to derive trust from such opinions. Some approaches, like [START_REF] Massa | A Trust-enhanced Recommender System application: Moleskiing[END_REF], represent a trust network by a labelled directed graph whose nodes represent agents, and where a directed edge from A to B with label d means that A rates B with d. Then the trust score that an agent A attaches to an unknown agent B is defined to be the weighted mean of the ratings given by those who had interactions with B.

One problem of these and similar numerical approaches is that they are based on several parameters, which may be hard, if not impossible, to identify correctly. Furthermore, a more cumbersome numerical perspective may also hide structural features and relationships, which could pave the way to a better understanding of the inferential processes. So there are a priori good reasons to investigate also more qualitative approaches.

A common strategy in this field has been to model the beliefs of the agents to derive trust relations between them, be it by using logical formalisms, like e.g. [START_REF] Castelfranchi | Principles of trust for MAS: Cognitive anatomy, social importance, and quantification[END_REF][START_REF] Cj | Belief, information acquisition, and trust in multi-agent systems: a modal logic formulation[END_REF], or quasi-probabilistic formalisms, like e.g. [START_REF] Jøsang | Trust-Based Decision Making for Electronic Transactions[END_REF][START_REF] Jøsang | A Logic for Uncertain Probabilities[END_REF]. However, we will take a slightly different direction and work within a framework which is -at least on the formal level -closer to that of Social Choice (see for instance [START_REF] Altman | On the Axiomatic Foundations of Ranking Systems[END_REF], which provides some interesting impossibility theorems). There one typically has a collection of agents, each of them ranking a set of alternatives. The main question is how to aggregate these local, personal rankings into a global, social one.

In the present work, we take a look at the particular case where the alternatives consist of the agents themselves, and where the personal rankings are binary, encoding high, respectively low trust. If agent A attributes the high rank to agent B, this means that A supports B and is willing to provide positive feedback on B. On the other hand, if A attributes the low rank, this only means that A does not support B, but not that there is explicit distrust, or actual negative feedback.

The paper is structured as follows. After introducing our basic framework, as well as our support tree concept, we formulate some basic requirements for preference relations over these trees. We are then going to describe two specific methods for deriving agent prioritizations from binary support relations. To conclude, we investigate whether they verify our postulates.

Basic framework

We start with a very simple model consisting of a set of agents A and a binary support relation ⊲ on A. Intuitively, ⊲ is meant to represent the explicit, visible, or reported support links among agents, with A ⊲ B telling us that A supports B. The question we are going address is the following: how can we use the support information encoded in the relation to estimate and compare the trustability of arbitrary agents. First some notation.

Definition 1 (Support structure) A support structure is an ordered pair (A, ⊲), where A is a non-empty finite set, and ⊲ a binary relation on A. The elements of A are called agents, and ⊲ is called the support relation.

Definition 2 (Support chain) Given a support structure (A, ⊲), an agent sequence (A 0 , . . . , A n ) with A i ⊲ A i+1 for i ≤ n -1 is called a support chain of length n from A 0 to A n over (A, ⊲). We say that A n receives (non-exclusively) nth-degree support from A 0 .

Our basic observation is that agents appear to be more trustable if they get support, not only from more agents, but also from agents which are themselves backed by other agents. In other words, more and/or longer support chains suggest more trustability. However, the impact of length and number can be limited by admissibility criteria. Consider for instance a support chain (A 0 , . . . , A n ) which starts and finishes with the same agent A 0 = A n . Of course, if n = 1, we tend to reject the chain as an instance of ruthless self-promotion. If n > 1, the situation is less obvious. Intuitively, it seems that while (A 0 , . . . , A n ) may still provide slightly more support than (A 1 , . . . , A n ), because of the circular dependency, it appears to be considerably less supportive than (A ′ 0 , A 1 , . . . , A n ), for A ′ 0 = A 0 . The actual contribution of circular support, from none to substantial, depends here on the exact interpretation of the support relation.

Nevertheless, for the basic approach, we are going to take a strict stance and ignore any -direct and indirect, i.e. higher degree -support from an agent to itself in the context of its support evaluation. That is, we consider a support chain from A 0 to A n to be inadmissible if A 0 = A n . Note however that this does not mean that we completely disregard the link from A 0 to A 1 . It may still have an impact on the support for other agents. Furthermore, the nth-degree support represented by the full chain may be seen as the combination of the ith-degree support for A i encoded by (A 0 , . . . , A i ) and the (ni)th-degree support for A n modeled by (A i , . . . , A n ). So, if (A 0 , . . . , A n ) is an admissible support chain, we would expect this to be true for (A 0 , . . . , A i ) and (A i , . . . , A n ) as well. It follows from this downwards closure condition that admissible support chains are not allowed to include an agent twice (at least in our basic framework). From now on, when we are going to refer to support chains, we will always mean admissible ones. Definition 3 (Admissibility) Let (A, ⊲) be a support structure. A support chain (A 0 , . . . , A n ) is said to be admissible iff for all i = j, we have

A i = A j .
Our strategy is to evaluate and compare the trustability of agents based on the admissible support chains over (A, ⊲) targeting them. Since the collection of support chains in favour of an agent A is closed under final segments, we can describe it in a natural and concise way by a tree, which we denote T A . Its nodes are the admissible support sequences with endpoint A, and its root is obviously (A). The sons of (A) are the admissible support chains of the form (A 1 , A), its grandsons those of the form (A 2 , A 1 , A), and so on. More formally: Definition 4 (Support tree) Let (A, ⊲) be a support structure and A ∈ A. The support tree of A over (A, ⊲), denoted by T A , is defined as T A = (N A , R), where

• N A (the set of nodes) consists of the admissible support chains (A 0 , . . . , A n ) over (A, ⊲) with A n = A,

• R (the edge/parent relation) is given by (

A n , . . . , A 0 )R(A ′ m , . . . , A ′ 0 ) iff m = n + 1, A i = A ′ i for i ≤ n, and A 0 = A ′ 0 = A.
If we label each node (A n , . . . , A 0 ) by its initial element A n , we see that it encodes the sequence of labels decorating the path connecting it to the root. Consequently, any support chain in favour of an agent A (= A 0 ) corresponds to a certain path in T A from a node to the root, and vice versa. In other words, the support tree for an agent A, with the above natural labeling, allows us to represent in a consise manner all the support chains in favour of A.

Here is an example with five agents linked by different support or trust relationships. First we give the initial support structure, and then we extract the resulting support trees for each agent. Note that in the tree representation, support is upwards directed.

T A T B T C T D T E
The next task will now be to see how we can use these support trees to prioritize agents in the context of a support structure.

Support tree comparison

We are now going to consider methods to estimate and compare the support which agents receive in the context of a given support structure. More specifically, we intend to achieve this through the evaluation of the support trees associated with agents. Their simple structure should allow us to get a better understanding of the basic prioritization issues, and also to pave the way for more fine-grained accounts, e.g. with numerical tags or processing circular support, which are beyond the scope of this paper.

Let T = (T A |A ∈ A) be the family of support trees derived from a given support structure (A, ⊲). The main step is to determine a suitable pre-order T on support trees which reflects the overall amount of support for their respective root agents, and thereby provides a prioritization of the agents in A. We observe that the agent labeling encodes dependency information which we may want to exploit. For instance, if an agent gets support from two other agents which are themselves supported, either by the same, or two different agents, its overall support seems to be lower in the former scenario. Within our present framework, keeping the evaluation elementary and tree-oriented, we ignore all the other, intrinsic properties of the labeling agents (except their identity). Note that the sub-tree structures below nodes sharing the same agent label may well diverge.

So the task is to find -in accordance with the support interpretation -intuitively appealing preference preorders over finite rooted trees whose nodes are labelled by agents A ∈ A. But before we are going to propose specific approaches, it may be helpful to formulate some general principles describing or guiding support tree comparison. We see several fundamental requirements for .

First, as we pointed out before, we restrict ourselves to exploit the structure of the support relation, but not any further characteristics of the labeling agents. Therefore, we should expect the preference relation to be invariant under renaming, i.e. a one-to-one exchange of labels. Accordingly, we propose the following structurality principle. For a function f on labels, and a finite rooted labelled tree T , let T f be the tree obtained by replacing each label l by its image f (l).

Invariance (I).

Let T and T ′ be two finite rooted labelled trees, and π, π ′ be bijections on the full set of labels. Then T

T ′ implies T π T ′ π ′ .
Thus, an exchange of labels does not affect the preference of trees. Of course, if we want to exploit the fact that the trees to be compared share certain labels, we have to consider a more permissive -because invariant under a smaller set of permutation pairs -version.

Weak Invariance (WI).

Let T and T ′ be two finite rooted labelled trees, and π be a bijection on the full set of labels. Then T T ′ implies T π T ′ π .

Of course, these conditions mainly reflect our structural perpective, and much less the nature of support.

Here one basic intuition would be that if an agent is directly supported by a bunch of other agents, and some of these get more support, then the overall support for the initial agent should increase as well, or at least stay the same. Let T A [T 1 , . . . , T m ] be the combined tree obtained by connecting the roots of the m rooted labelled trees T j to a new superroot labelled by a new agent A.

Structural Monotony (SM). If T j

1

T j 2 holds for each 1 ≤ j ≤ m, and the T j 1 are distinct iff the T j 2 are, then

T A [T 1 1 , . . . , T m 1 ] T A [T 1 2 , . . . , T m 2 ]
. As usual, we define T 1 ≺ T 2 iff T 1 T 2 and not T 2 T 1 .

Strict Structural Monotony (SSM).

Suppose SM holds. If T j 1 T j 2 holds for each 1 ≤ j ≤ m, and the T j 1 are distinct iff the T j 2 are, and T j 1 ≺ T j 2 for at least one j, then

T A [T 1 1 , . . . , T m 1 ] ≺ T A [T 1 2 , . . . , T m 2 ]
. In some sense, SSM implements a more additive philosophy for support. To take off, these requirements need however another core principle which roughly states that support is preferable to non-support.

Non-triviality (NT).

Let T B be a labelled tree consisting of a single node.

If A = B, then T A [T B ] ≺ T B .
In a first step, we would propose the following -non-exhaustive -list of basic rationality postulates for :

• WI, SSM (hence also SM), and NT.

Comparison strategies

We are now going to present two simple methods for evaluating the relative trustability of agents by comparing their support trees in the context of a given support structure (A, ⊲). In the present paper, this amounts to specify preference relations over finite labelled rooted trees which are compatible with our intuitions about support/trust. We emphasize that these proposals are mainly meant to illustrate our conceptual framework without too much technical luggage. Both procedures are based on lexicographic and cardinality considerations. This has the advantage that we may not have to construct the entire trees to compare them.

Agent Strategy

The first approach compares the number of agents supporting (directly/indirectly) the root agent, but focusing on the lowest-degree support, which intuitively appears to be the most reliable (proximity to the object of judgment), and therefore the most important one. ith-degree -but not jth degree for j < i -support to A. The inductive construction of this layering is unproblematic. Obviously, the definition applies to arbitrary labelled trees.

The idea is now to say that the contribution of a single agent providing ith-degree support to the trustability of a root agent outweighs the contributions of an arbitrary number of agents providing jth-degree support, for j > i, to the trustability of any root agent. This gives us a dominance relation across support trees. Consequently, according to this view, A is more trustable than B if and only if there exists an i such that S i A has more elements than S i B , and for each j < i, S j A has the same cardinality as S j B . Here is a formal definition based on support trees: Definition 5 (Agent strategy) Let T A , T B be two rooted labelled trees. We say that T A is preferred to T B w.r.t. the agent-strategy, in symbols T A ≺ a T B , iff there is an i with

|S i A | < |S i B |
, and for all j < i,

|S j A | = |S j B |. We set a = ≺ a ∪ =.
Definition 6 (Agent-trustability) Let (A, ⊲) be a support structure, A, B ∈ A. We say that A is more trustable than B w.r.t. the agent-strategy, in symbols

A < a B, iff T A ≺ a T B .
It is easy to see that < a provides a stratification of the agents reflecting their trustability. For instance, in the previous example there are five layers: first B, second D, third A, fourth C, and fifth E.

Chain strategy

Another possible strategy is to consider each support chain in favour of an agent in itself as a contribution to the agent's trustability. In other words, instead of counting the number of agents supporting A or B, we may count the number of chains targeting A or B. The idea here is similar to the previous one insofar as it says that the contribution of the starting point of a single chain of length i supporting A outweighs the contributions of the starting points of an arbitrary number of chains of length j > i supporting B. More formally:

Definition 7 (Chain strategy) Let T A , T B be two rooted labelled trees. We say that T A is preferred to T B w.r.t. the chain strategy, in symbols T A ≺ c T B , iff there is an i such that the number of nodes at depth i in T A is larger than that in T B , and for each j < i, there is an equal number of nodes at depth j in T A and T B . We set c = ≺ c ∪ =.

Definition 8 (Chain trustability) Let (A, ⊲) be a support structure, A, B ∈ A. We say that A is more trustable than B w.r.t. the chain strategy, in symbols A < c B, iff T A ≺ c T B .

Again < c provides a stratification of the agents reflecting their trustability. In the above example, we get again five layers, but different ones: first A, second B, third D, fourth C, and fifth E

To conclude, we want to see to what extent these two elementary approaches verify the principles we formulated for the comparison of support trees.

Proposition 9 (Principles)

1. a verifies NT, I, WI, but not SM, SSM.

c verifies NT, I, WI, SM, SSM.

While both approaches have some technical and conceptual drawbacks, which may be expected given the straightforward definitions, the chain strategy is at least in line with our basic postulates.

As far as we can tell, there is no model in the literature producing exactly the same inferential results, in particular because of our handling of cycles. The exact relationship with other accounts, as well as the evaluation of competing proposals within our framework, will be addressed elsewhere.

  For two agents A, B ∈ A, let deg(A, B) be the length of the smallest support chain from B to A, if there is one. If there is none, we set deg(A, B) = ∞ if A = B, and deg(A, B) = 0 if A = B. Let S i A = {B ∈ A | deg(A, B) = i} be the set of agents which provide


Martin Caminada

Jonathan Ben-Naim

Postulates for Paraconsistent Reasoning and Fault Tolerant Logic Programming *

In this paper we examine, from an abstract point of view, a number of properties to be satisfied not only by formalisms for paraconsistent reasoning, but also for formalisms that aim to improve on logic programming by warranting the existence of models.

Introduction

Paraconsistent logic can be described as a series of approaches to meaningful formal reasoning in the presence of possibly conflicting information [START_REF] Belnap | A useful four-valued logic[END_REF][START_REF] Belnap | How computers should think[END_REF][START_REF] Arieli | The value of the four values[END_REF]. An important though often neglected question is what it exactly is that one aims to achieve with a formalism for paraconsistent reasoning. That is, what are the important properties a formalism for paraconsistent reasoning should satisfy? An abstract treatment of this issue is important not only for the existing field of propositional and first order paraconsistent reasoning, but also for the field of logic programming and answer set programming, where similar problems occur.

This paper is structured as follows. First, in section 2, we provide three general postulates that we feel each formalism for paraconsistent reasoning should minimally support. Then, in section 3, an analysis is given of which existing paraconsistent logics support which of the postulates in section 2. In section 4, we broaden the discussion to include semantics for logic programming. It will be shown that some of the issues in paraconsistent logic also play a role in logic programming. In section 5, we round off the discussion with a summary of the main results.

The Postulates

In order for the postulates to be applicable to a broad range of formalisms, we define the basic concepts in a very general way. Definition 1. Let L be the language of a logical formalism, composed using a countably infinite set of atoms and a finite number of logical operators. Let F be the set of all wellformed formulas in L. Let be the entailment operator of this formalism. Let S ⊆ F We define Cn(S) to be {c | S c}.

Examples of logical formalism that satisfy Definition 1 are:

• classical propositional logic • propositional default logic, using the sceptical or credulous approach • grounded normal logic programs under the well-founded semantics

• grounded normal logic programs under the stable model semantics, using the sceptical or credulous approach

• grounded extended logic programs under answer set semantics, using the sceptical or credulous approach

In the following definitions, we write atoms(S) for the atoms that occur in a set of formulas S. For instance: atoms(p ∧ q; r ∨ p) = {p, q, r} and atoms(p ← q; r ← s, t)) = {p, q, r, s, t}. Furthermore, if A is a set of atoms and S a set of formulas then we write S |A for those formulas in S that contain only atoms from A. For instance: {p ∧ q; q ⊃ r; s ∨ t; q} |{p,q} = {p ∧ q; q}.

The first property to be stated is that of non-interference. Non-interference roughly means that, for two completely independent knowledge bases S 1 and S 2 , S 1 does not influence the outcome with respect to the language of S 2 .

Definition 2 (non-interference). We say that a logical formalism satisfies non-interference iff for every two sets of formulas S 1 and S 2 such that atoms(S 1 ) ∩ atoms(S 2 ) = ∅ it holds that Cn(S 1 ) |atoms(S1) = Cn(S 1 ∪ S 2 ) |atoms(S1) and Cn(S 2 ) |atoms(S2) = Cn(S 1 ∪ S 2 ) |atoms(S2) .

A property closely related to non-interference is that of contamination. Informally, a set of formulas is said to be contaminating iff it yields the same outcome when merged with a totally unrelated set of formulas. That is, a contaminating set of formulas makes all other unrelated sets of formulas irrelevant when being merged with it.

Definition 3 (contamination).

A set of formulas S 1 , with atoms(S 1 ) = atoms(F), is called contaminating iff for any set of formulas S 2 such that atoms(S 1 ) ∩ atoms(S 2 ) = ∅ it holds that Cn(S 1 ) = Cn(S 1 ∪ S 2 ).

Based on the concept of contamination, it is then possible to define the property of crash resistancy.

Definition 4 (crash resistancy). We say that a logical formalism satisfies crash resistancy iff there does not exist a set of formulas S that is contaminating.

The property of crash resistancy is perhaps best understood by examining what crashes commonly mean in software engineering and operating systems. As any experienced computer user knows, it sometimes can occur that a program misbehaves. Under some operating systems, however, the fact that one program misbehaves (like executing illegal instructions) causes the entire operating system to collapse, which then also has consequences for all other programs that were running, even if they are totally unrelated to the program that caused the original problem. The main point here is that one wants to avoid local problems having global effects, and rendering all other things irrelevant. It is this property that is expressed in the above definition of crash resistancy.

The last property to be discussed is that of backwards compatibility. The idea is, roughly, that a formalism (like paraconsistent logic) is to improve on an existing, possibly non crash resisting formalism (like propositional logic) it should yield the same outcome for all non-contaminating input in the latter formalism.

Definition 5 (backwards compatibility).

Let LF 1 and LF 2 be two logical formalisms that use the same language. We say that LF 2 is backwards compatible with LF 1 iff for every finite set S that is not contaminating in S 1 , it holds that Cn LF1 (S) = Cn LF2 (S).

Logics for Paraconsistent Reasoning

Paraconsistent logics have been introduced to overcome a weakness of classical logic, namely there is no classical model for certain sets of formulas (called inconsistent sets) and therefore everything can be concluded from them. Note that this is more a convention to keep an elegant definition than an intuitively motivated choice. Many directions of research have been explored to remedy this problem. Some approaches are based on possible worlds semantics, for example, the non-adjunctive logics and the relevance logics. Some, called non truth-functional logics, still define an interpretation as a function v from the language considered to "true" and "false", like classical logic. But, the constraints on v are weakened, in particular the truth value of ¬α is not fully determined by that of α. Last but not least, some define an interpretation as a function from the language to many epistemic states (e.g. "informed that true", "informed that false", "informed of both", "no information"). They are called the many-valued logics.

All of the above approaches aim at avoiding contaminating sets of formulas. However, as far as the authors know, only the many-valued community proposed some logics that are backward compatible with classical logic. In our opinion, one of the most interesting solution is the preferential version of the logic of Belnap [START_REF] Belnap | How computers should think[END_REF][START_REF] Belnap | A useful four-valued logic[END_REF] proposed by [START_REF] Arieli | The value of the four values[END_REF]. Let us first recall very briefly some elements of classical logic. Let L be the language consisting of a set of propositional symbols (or atoms) A and the usual connectives ¬ and ∨. Let F be the set of all well-formed formulas of L. A classical valuation of L is a function v from F to {0, 1} (i.e. "false" and "true") such that ∀ α, β ∈ F the following holds:

v(α) = 1 iff v(¬α) = 0; v(α ∨ β) = 1 iff v(α) = 1 or v(β) = 1. A classical model of a set of formulas Γ is a valuation v such that ∀ α ∈ Γ, v(α) = 1.
The classical consequence relation for L is the relation c on P(F) × F such that ∀ Γ ⊆ F, ∀ α ∈ F, Γ c α iff every model for Γ is a model for α.

It turns out that c is not crash resistant because every inconsistent set of formulas is contaminating. As said previously, paraconsistent reasoning has been developed to overcome this problem. The logic of Belnap [START_REF] Belnap | A useful four-valued logic[END_REF][START_REF] Belnap | How computers should think[END_REF] plays an important role in this field. It uses four epistemic states denoted by {1}, {0}, ∅, {0, 1}. There are many possible meanings for them. Some authors see them as respectively "true", "false", "neither true nor false", "both true and false". Some others see them as the elements of a certain bilattice representing degrees of knowledge and degrees of truth. But, we prefer by far the intuitive meaning that follows.

Imagine some sources of information talking about the atoms (not the compound formulas). For each atom p, a source can tell that p is true, or that it is false, or nothing about p. We consider that an atom is globally told to be true (false) iff some source tells that. Then, we develop this global information in the following way: if a formula α is told to be true (false), then ¬α is implicitly told to be false (true), and vice versa. In addition, if at least one of α and β is told to be true, then so is α ∨ β. Note that the converse is not required as it would be counter-intuitive, however we automatically get it as the sources can talk only about the atoms. Finally, if both α and β are told to be false, then so is α ∨ β, and vice versa. This global and developed information constitutes a valuation in the logic of Belnap.

More formally, a Belnap valuation is a function v from F to P({0, 1}) such that ∀α, β ∈ F,

1 ∈ v(¬α) iff 0 ∈ v(α) 0 ∈ v(¬α) iff 1 ∈ v(α) 1 ∈ v(α ∨ β) iff 1 ∈ v(α) or 1 ∈ v(β) 0 ∈ v(α ∨ β) iff 0 ∈ v(α) and 0 ∈ v(β)
Intuitively, 1 ∈ v(α) (resp. 0 ∈ v(α)) means that α is told to be true (resp. false). In fact, a Belnap valuation represents, for some sources of information, the global and developed information obtained from what they say by the manner explained previously. A Belnap model of a set of formulas Γ is a Belnap valuation v such that ∀ α ∈ Γ, 1 ∈ v(α). The consequence relation of Belnap, denoted by B , is defined in the following usual way:

∀ Γ ⊆ F, ∀ α ∈ F, Γ B α iff every Belnap model of Γ is a Belnap model of α.
It is easy to see that this logic is crash resistant for our simple language L. However, it is not backward compatible with classical logic. Indeed, for instance, {α, ¬α ∨ β} c β whilst {α, ¬α ∨ β} B β. That is why Arieli and Avron proposed a preferential version. The idea is to consider that the epistemic states {0} and {1} are preferred to ∅ and {0, 1}. Consequently, [START_REF] Arieli | The value of the four values[END_REF] introduced the preferential relation ≺ such that for any two Belnap valuations v and w:

v ≺ w (v is preferred to w) iff {p ∈ A : w(p) is {0} or {1}} ⊂ {p ∈ A : v(p) is {0} or {1}}.
Then, given a set of Belnap valuations V , an element v of V is said to be preferred (in V ) iff there is no element of V which is preferred to v.

This leads to the preferential consequence relation p such that ∀ Γ ⊆ F, ∀ α ∈ F, Γ p α iff every preferred Belnap model of Γ is a Belnap model of α. It can be checked that p is both crash resistant and backwards compatible with classical logic. The same kind of construction can be done with the standard three-valued logic [START_REF] Bench-Capon | Sur un problème de Jaśkowski[END_REF]. More generally, the efforts devoted to the study of such logics emphasize the importance of those properties in the field on non-monotonic reasoning.

Logic Programming

It is interesting to observe that in the field of logic programming, similar problems play a role as in the field of paraconsistent logic. Under the stable model semantics [START_REF] Gelfond | The stable model semantics for logic programming[END_REF] the program S 1 = {a ← not a} is contaminating, since it yields the same outcome when it is merged with an arbitrary syntactically disjunct program S 2 (for instance S 2 = {b ← not c}). S 1 as well as S 1 ∪ S 2 do not have any stable models. Therefore, the set of credulously accepted statements is ∅ and the set of sceptically accepted statements is the set of all literals.

Some alternative approaches to logic programming, such as the well-founded semantics [START_REF] Allen Van Gelder | The well-founded semantics for general logic programs[END_REF] actually satisfy non-interference and crash resistancy. At the same time, it must be mentioned that the well-founded semantics, as well as approaches like [START_REF] Przymusinski | The well-founded semantics coincides with the three-valued stable semantics[END_REF][START_REF] You | A three-valued semantics for deductive databases and logic programs[END_REF], are not backwards compatible with the now well-established stable model semantics. For instance, the program a ← not b b ← not a c ← not b, not c has a unique stable model {b} whereas its well-founded model is the empty set.

We know of no existing formal semantics for logic programming that satisfies crash resistancy and non-interference, while at the same time being backwards compatible with stable model semantics. Nevertheless, such a semantics would be far from impossible. Caminada, for instance, proposes the semi-stable semantics for abstract argumentation [START_REF] Caminada | Semi-stable semantics[END_REF]. Semi-stable semantics satisfies crash resistancy and non-interference, and is backwards compatible with stable semantics. As logic programming can be seen as an instantiated form of abstract argumentation [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], this means that we can directly apply semi-stable semantics as a foundation for logic programming. This will then yield a semantics that satisfies non-interference and crash resistancy and is backwards compatible with the stable model semantics. How such could exactly be done is a topic for further research.

Summary

In this paper, we have stated three postulates that can be applied to paraconsistent reasoning as well as to logic programming. It was observed that the original paraconsistent logic of Belnap [START_REF] Belnap | A useful four-valued logic[END_REF][START_REF] Belnap | How computers should think[END_REF] satisfies crash-resistancy but not backwards compatibility. The approach of Arieli and Avron [START_REF] Arieli | The value of the four values[END_REF], at the other hand, satisfies both properties.

As for logic programming, it was observed that the stable model semantics does not satisfy crash-resistancy. Approaches like the well-founded semantics [START_REF] Gelfond | Classical negation in logic programs and disjunctive databases[END_REF] and that of [START_REF] Przymusinski | The well-founded semantics coincides with the three-valued stable semantics[END_REF][START_REF] You | A three-valued semantics for deductive databases and logic programs[END_REF] do satisfy crash resistancy but are not backwards compatible with the stable model semantics. However, it appears that a relatively new semantics (semi-stable, [START_REF] Caminada | Semi-stable semantics[END_REF]) could be applied to logic programming to yield an approach that is not only crash resistant, but is also backwards compatible with the stable model semantics. This would make semi-stable semantics a very suitable candidate for fault-tolerant Answer Set Programming.

This work was partly supported by the EU ASPIC project