Nicolas Hug
email: nicolas.hug@irit.fr

Henri Prade
email: henri.prade@irit.fr

Gilles Richard
email: gilles.richard@irit.fr

Mathieu Serrurier
email: mathieu.serrurier@irit.fr

Analogy in Recommendation. Numerical vs. Ordinal: a Discussion

The paper investigates the use of analogical reasoning for recommendation purposes. More particularly, we address the problem of predicting missing ratings on the basis of known ones. After discussing the differences with another recently experimented approach based on analogical proportions, a new analogical approach is proposed. It relies on the intuition that "the rating of user u for item i is to the rating of user v for item i as the rating of user u for item j is to the rating of user v for item j". This leads to algorithms yielding results close to the ones of state-of-the art approaches, when the ratings are regarded as numerical quantities. This is due to the fact that these latter approaches embed an estimation process that is implicitly close to analogy, as discussed in this paper. An analogical approach is also outlined and briefly discussed when the ratings are supposed to have an ordinal meaning only.

I. INTRODUCTION

Recommendation may refer to a variety of problems depending on the information available. One may try to propose items or products on the basis of their descriptions to users whose preferences profiles are known. One may also take advantage of the behavior of other users that are similar to the recommendee. One may also try to predict missing ratings on the basis of known ratings. Exploiting preferences may call for fuzzy set methods; see, e.g. [START_REF] Perny | Preference-based search and machine learning for collaborative filtering: the "film-conseil movie recommender system[END_REF], for an early example. Similarity is also a graded notion that underlies case-based reasoning, which can be embedded in a fuzzy rule-based approach and be related to k-nearest neighbor approaches [START_REF] Dubois | Fuzzy set-based methods in instance-based reasoning[END_REF], [START_REF] Hüllermeier | Model adaptation in possibilistic instance-based reasoning[END_REF], [START_REF] Dubois | Fuzzy methods for case-based recommendation and decision support[END_REF].

The recommendation problem considered in this paper is the prediction of missing ratings on the basis of known ratings. We more particularly explore the idea of applying analogical reasoning to this problem. Analogy is used here in terms of analogical proportions, i.e., statements of the form "a is to b as c is to d". In case-based reasoning, situations with known conclusions are put in parallel one by one, with a new pair (situation 0, conclusion 0) where 'conclusion 0' is unknown. Then case-based reasoning can be viewed as a particular instance of analogical reasoning since one can say that "conclusion 0 should be to conclusion i as situation 0 is to situation i". However there is a more sophisticated way to apply analogy here, namely to state that "(situation 0, conclusion 0) is to (situation 3, conclusion 3) as (situation 2, conclusion 2) is to (situation 1, conclusion 1)", which requires to put the situation on which one wants to conclude in parallel with three other situations where the corresponding conclusion is known [START_REF] Dubois | Case-based and analogical reasoning[END_REF]. Then using a formal model of an analogical proportion [START_REF] Miclet | Logical definition of analogical proportion and its fuzzy extensions[END_REF], [START_REF] Prade | From analogical proportion to logical proportions[END_REF], and observing that analogical proportions hold on various features describing the four situations, one conclude that "conclusion 1 is to conclusion 2 as conclusion 3 is to conclusion 0" should hold as well, which leads to compute 'conclusion 0' from this latter relation.

The idea of applying analogy to recommendation is not entirely new. Thus, Sakaguchi et al. [START_REF] Sakaguchi | Recommendation system with multidimensional and parallel-case four-term analogy[END_REF] use four-terms analogy in a case-based reasoning style for proposing dishes to users, while three of the authors of the present paper have more recently proposed a 4-(situation, conclusion)-based analogical mechanism for predicting missing ratings on the basis of known ratings [START_REF] Hug | Experimenting analogical reasoning in recommendation[END_REF]. This latter work yielded reasonably good results, but was extremely heavy computationally speaking. In this paper, we investigate a more tractable way of using analogical proportions for solving the same problem. Namely, letting r ui be the rating for item i by user u, we assume that "r ui is to r vi as r uj is to r vj , where r vj is unknown, while the three other ratings are available. We shall first consider the ratings as numbers, which leads to an estimation process quite close to the one used in Takagi-Sugeno fuzzy rule-based controllers [START_REF] Takagi | Fuzzy identification of systems and its application to modelling and control[END_REF] where similarity-based weighted averages are performed. We then more briefly discuss the case where the ratings are only considered as having an ordinal meaning.

The paper is structured as follows. The next section provides the necessary background on the modelling of analogical proportions when features are Boolean and when they are numerical. Section 3 first recalls the previously proposed analogical approach to the prediction of missing ratings which uses the sophisticated mechanism involving four parallel vectors of the (situation, conclusion)-type. Then Section 3 introduces the way analogy is applied in this paper. Section 4 presents the algorithm that exploits this view and reports results of experiments on the Movielens benchmark when the ratings are regarded as numerical quantities. These results are quite close to the ones obtained by state-of-the art approaches. This is due to the fact that the proposed analogical approach appear to be formally very close to the state-of-the art approaches, although the latter do not refer to analogy at all, as revealed by the discussion ending the section. Section 5 outlines an ordinal counterpart to the proposed analogical approach, since it is arguable that ratings have often mainly an ordinal meaning.

II. ANALOGICAL REASONING WITH PROPORTIONS

The following section provides the necessary background on analogical reasoning that will be used throughout this paper.

A. Formal definitions

An analogical proportion "a is to b as c is to d" states analogical relations between the pairs (a, b) and (c, d), as well as between the pairs (a, c) and (b, d). There are numerous examples of such statements, with which everybody will more or less agree, such as "calf is to cow as foal is to mare", or "brush is to painter as chalk is to teacher". However, it is only rather recently that formal definitions have been proposed for analogical proportions, in different settings [START_REF] Yvon | Formal models of analogical proportions[END_REF], [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF], [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF]. For more details, see [START_REF] Prade | From analogical proportion to logical proportions[END_REF], [START_REF] Prade | Analogical proportions and multiple-valued logics[END_REF], [START_REF] Prade | Homogenous and heterogeneous logical proportions[END_REF].

It has been agreed since Aristotle time, taking lesson from geometrical proportions, that an analogical proportion T , as a quaternary relation, satisfies the three following characteristic properties:

1 In the following, we will be mostly interested in the arithmetic proportions in R or in R n , and will work with analogies between ratings.

B. Using analogical proportion for inference

To understand how one can infer new information on the basis of analogical proportions, we need to define the equation solving process. The equation solving problem amounts to finding a fourth element x to make the incompletely stated proportion a : b :: c : x to hold. As expected, the solution of this problem depends on the target model. For instance, in the case of extended arithmetic proportions, the solution always exists and is unique: x = b -a + c. In terms of geometry, this simply tells us that given 3 points, we can always find a fourth one (aligned with, or in the same plan as a, b, c) to build a parallelogram.

The analogical inference principle is, logically speaking, an unsound inference principle, but providing plausible conclusions [START_REF] Prade | Reasoning with logical proportions[END_REF]. It postulates that, given 4 vectors a, b, c, d such that the proportion holds on some components, then it should also hold on the remaining ones. This can be stated as (where a = (a 1 , a 2 , • • • a n ), and J ⊂ [1, n]): ∀j ∈ J, a j : b j :: c j :

d j ∀i ∈ [1, n] \ J, a i : b i :: c i : d i (analogical inf erence)
This principle leads to a prediction rule in the following context:

• 4 vectors a, b, c, d are given where d is partially known: only the components of d with indexes in J are known. • Using analogical inference, we can predict the missing components of d by solving (w.r.t. d i ) the set of equations (in the case they are solvable):

∀i ∈ [1, n] \ J, a i : b i :: c i : d i .
In the case where the items are such that their last component is a label, applying this principle to a new element d whose label is unknown leads to predict a candidate label for d. This prediction technique has been successfully applied to classification problems in both Boolean [START_REF] Bayoudh | Learning by analogy: A classification rule for binary and nominal data[END_REF] and numerical settings [START_REF] Prade | Enforcing regularity by means of analogy-related proportions-a new approach to classification[END_REF], thus suggesting promising results in the recommendation task.

III. ANALOGY AND THE RECOMMENDATION PROBLEM

This section provides some necessary background on the recommendation task, and explores various ideas that can be developed to build an analogical reasoning-based recommender system.

A. Recommendation as prediction of missing ratings

Let us formalize the problem of recommendation. Let U be a set of users and I a set of items. For some pairs (u, i) ∈ U × I, a rating r ui is supposed to have been given by u to express if he/she likes or not the item i. R denotes the set of all known ratings. Let U i be the set of users that have rated item i, and I u is the set of items that user u has rated. I uv defines the set of items rated by both users u and v. The ultimate goal of a recommender system is to provide relevant and personalized recommendations of items to users, and this is usually done by trying to predict users' ratings for any item in the the system. Note that users and items can play symmetrical roles: indeed, one can see the recommendation problem as recommending items to users or as recommending users to items. In the following, we chose the first view which we find more intuitive for the reader.

The two main families of recommender systems are contentbased methods where some meta data describing users and items are used, and collaborative filtering methods, much more popular, where predictions are computed by taking into account the social environment of users which is usually modeled by the ratings they gave. Collaborative techniques are the one we are interested in here, as they have shown to outperform the content-based ones.

It is quite common that ratings belong to [0, 1] or to [START_REF] Perny | Preference-based search and machine learning for collaborative filtering: the "film-conseil movie recommender system[END_REF][START_REF] Dubois | Case-based and analogical reasoning[END_REF], while 1 is the worst rating and 5 meaning a strong preference. It is not always clear whether this rating scale should be interpreted as purely numerical, or more like an ordinal scale when it comes to develop prediction algorithms. This is a question that we will address throughout this paper.

When ratings are treated as numerical quantities, the two most used performance evaluation metrics are MAE (Mean Absolute Error) and RMSE (Root Mean Squared Error), and are usually computed using cross validation:

MAE = 1 |R| • rui |r ui -r ui | (1) RMSE = 1 |R| • rui (r ui -r ui ) 2 (2)
They both evaluate how close predictions are from their true values, RMSE being much more penalizing over big errors.

B. Analogical proportions between users

Using analogical reasoning for recommendation as been studied in [START_REF] Hug | Experimenting analogical reasoning in recommendation[END_REF]. Authors strictly follow the analogical inference principle described in section II-B for making predictions, using analogical proportions between users.

The main idea is that if an analogical proportion stands between four users a, b, c, d, meaning that for each item j that they have commonly rated, the analogical proportion r aj : r bj :: r cj : r dj holds, then it should also hold for an item i that a, b, c have rated but d has not (i.e. r di is the missing component). This leads us to estimate r di as the solution x = rdi of the following analogical equation:

r ai : r bi :: r ci : x.
Given a pair (u, i) such that r ui / ∈ R (i.e. there is no available rating from user u for item i), the main procedure is as follows:

1) find the set of 3-tuples of users a, b, c such that an analogical proportion stands between a, b, c, and u and such that the equation r ai : r bi :: r ci : x is solvable. 2) solve the equation r ai : r bi :: r ci : x and consider the solution x as a candidate rating for r ui . 3) set rui as an aggregate of all candidate ratings. This technique has shown to be not too far from basic collaborative filtering approaches [START_REF] Hug | Experimenting analogical reasoning in recommendation[END_REF], but suffers of its inherent cubic complexity which makes it impossible to look for every possible 3-tuples of users, thus compromising the prediction accuracy.

C. Pairwise analogy between clones

Considering analogy between four users has shown to be computationally intensive, thus not really suitable for recommendation purposes, where time is a highly critical dimension. Yet, other forms of analogy can be addressed in the recommendation task, based on the observation that some users may be more inclined to give good (or bad) ratings than others. Indeed, ratings are in no way absolute and greatly depend on the subjective appreciation each user has about the rating scale. In the [START_REF] Perny | Preference-based search and machine learning for collaborative filtering: the "film-conseil movie recommender system[END_REF][START_REF] Dubois | Case-based and analogical reasoning[END_REF] scale for example, two users u and v might semantically agree on an item i describing it as bad, but there is a chance that this agreement is not perfectly reflected in the ratings: u might have rated i with r ui = 1 and v with r vi = 3, simply because from v' point of view 3 is a bad rating, while for u a rating of 3 would simply mean decent or good enough. In the following, we refer such users that semantically agree on their common items (but not necessarily numerically) as clones, as illustrated in Figure 1. Please note that the word clone is not used here to mean strictly identical, but more in the sense that two clones are two users following parallel paths. It is obvious that in collaborative filtering, clones are of great interest when it comes to predict a user's ratings, and yet the information they provide is often discarded. The principle underlying the analogical clone-based view is the following: for predicting a missing rating for u we not only look at its nearest neighbors, but also to those v whose rating are such that r ui = r vi + t vu where t vu is a more or less constant correction term that can be either positive or negative.

In the next two sections, we investigate this idea of a clonebased prediction, first when ratings are viewed as numerical quantities in section IV, and then when they have an ordinal meaning only in section V.

IV. RATINGS AS NUMERICAL QUANTITIES

In the following, we define C i (u) as the set of users that are clones of u and that have rated item i. From the previous definitions, one can easily derive a very general collaborative filtering framework for predicting a user's rating by taking into account its clones:

rui = aggregation(r vi + t vu ), ∀v ∈ C i (u),
where t vu is a correction term that we need to add to v's ratings so that they correspond to those of u. We clearly have a generalization of the k-NN approach, which we could write as:

rui = aggregation(r vi + t vu ), ∀v ∈ {v ∈ C i (u)|t vu = 0}.
Following this general framework, one can construct a great variety of algorithms with various level of complexity. In the next subsections, we propose a very straightforward algorithm, and a more efficient one.

A. A straightforward prediction algorithm

In its most simple form, a user v can be considered to be a t-clone of u if the ratings of v differ from those of u from a constant t:

v ∈ t-C(u) ⇐⇒ ∀i ∈ I uv , r ui = r vi + t. (3)
From then on, computing rui amounts to finding all the users v that satisfy this criteria, and computing an aggregation of their rating for i, which can simply be a mean. We implemented this basic algorithm described by algorithm 1, and referred to as Bruteforce.

Algorithm 1 Bruteforce

Input: A set of known ratings R, a user u, an item i such that r ui / ∈ R. Output: rui , an estimation of r ui Init: x Of course, one may want to relax the definition of a tclone, as the current one is too strict and only very few users will satisfy this criteria. In our implementation, we chose the following condition:

C = ∅ // list
v ∈ t-C(u) ⇐⇒ i∈Iuv |(r ui -r vi ) -t| ≤ |I uv |.
This amounts to accept v as a t-clone of u if on average, r ui -r vi is equal to t with a margin of 1.

The values of t clearly depend on the rating scale. The dataset on which we tested our algorithms use the [START_REF] Perny | Preference-based search and machine learning for collaborative filtering: the "film-conseil movie recommender system[END_REF][START_REF] Dubois | Case-based and analogical reasoning[END_REF] interval, so possible values for t that were considered are integer values between [-4, 4]. This is obviously a very rough algorithm, to which one could point out numerous flaws, but its purpose is to show that even such a basic clone-based approach can lead to better results than a basic neighborhood method.

B. Modeling clones with the similarity measure

Another option to consider clones is to use the well known neighborhood-based formula, and capture their effect inside an appropriate similarity measure. The general neighborhood formula is as follows [START_REF]Recommender Systems Handbook[END_REF]:

rui = v∈N k i (u) r vi • sim(u, v) v∈N k i (u) sim(u, v)
, where N k i (u) is the set of the k nearest neighbors of u that have rated i. So, we move from a crisp view of the set of clones to a fuzzy one. In fact, the above formula looks very similar to the interpolation principle underlying Takagi-Sugeno fuzzy controller where similarity degree is viewed as a fuzzy membership grade [START_REF] Takagi | Fuzzy identification of systems and its application to modelling and control[END_REF].

The above formula is commonly used with classical similarity metrics such as Pearson or cosine similarity, or inverse of MSD (Mean Squared Difference, which is a distance). However, these similarities are not plainly satisfactory when it comes to clones. Indeed with these metrics, two users are considered to be close if their common ratings are often the same, but two perfect clones u and v with a significant correction term t vu would be considered as far from each other, thus involving a loss of information.

A simple choice to measure how two users relate as clones can be the following:

Clone dist(u, v) = 1 |I uv | • i∈Iuv ((r ui -r vi ) -µ uv ) 2
where µ vu is the mean difference between ratings of u and v:

µ uv = 1 |I uv | i∈Iuv (r ui -r vi ).
One can understand this distance in two ways:

• it can be regarded as the variance of the difference of ratings between u and v, • or it can be regarded as a simple MSD measure

(MSD(u, v) = 1 |Iuv| • i∈Iuv (r ui -r vi ) 2
) to which the mean difference of ratings between u and v has been subtracted.

As our measure Clone dist is a distance, it is necessary to transform it into a similarity measure. Common choice is to take its inverse (while accounting for zero division):

Clone sim(u, v) = 1 Clone dist(u,v)+1 .
Once we know how to find the clones of a user, it is a simple matter to output a prediction using the classical neighborhood approach:

rui = v∈N k i (u) (r vi + µ uv ) • sim clone(u, v) v∈N k i (u) sim clone(u, v)
. This algorithm will be referred to as CloneA. For the sake of completeness, we also tried the same formula but with a more basic similarity metric that does not care about clones: MSD. This algorithm is referred to as CloneB.

C. Current practices in neighborhood-based methods

A simple and efficient formula using neighborhood technique, popularized by [START_REF] Koren | Factor in the neighbors: Scalable and accurate collaborative filtering[END_REF] is the following:

rui = b ui + v∈N k i (u) (r vi -b vi ) • sim(u, v) v∈N k i (u) sim(u, v) .
It is based on a simple k-NN approach, where are added the b ui terms, called baselines: b ui = µ+b u +b i . µ is the global mean of all ratings in R. The b u term is intended to capture users propensity to give ratings higher or lower than the global mean µ, and the same goes for items with b i : some items tend to be rated higher than others. Baselines are computed by solving a least squares problem:

min bu,bi rui∈R (r ui -(µ + b u + b i )) 2 ,
which can be achieved efficiently by stochastic gradient descent, or alternating least squares.

Among recommended similarity metrics, this one is of particular interest:

sim(u, v) = i∈Iuv (r ui -b ui ) • (r vi -b vi ) i∈Iuv (r ui -b ui ) 2 • i∈Iuv (r vi -b vi ) 2 .
It is simply a Pearson correlation coefficient, except that instead of centering ratings by their means, they are centered with the baseline predictors. An intuitive and illuminating way to look at this algorithm as a whole is to see that it conceptually follows these steps:

1) Compute R ′ , the set of all ratings normalized by the corresponding baseline: r ′ ui = r ui -b ui . R ′ can be regarded as the set where all ratings are given from the same frame of reference, thus discarding any bias. In R ′ , ratings can then be considered as absolute.

2) Using R ′ , compute similarities between users using the cosine similarity (the cosine similarity is the same as the Pearson correlation coefficient, except that quantities are not centered). 3) Output a prediction using the basic k-NN formula. As this prediction belongs to the same space of R ′ where ratings have no bias, it needs to be transposed back to the space of R (for performance evaluation purposes). In what follows, this algorithm is referred to as k-NNbsl. It is very clear that the use of the baseline predictors is motivated by the same reasons one would want to consider clones in a rating prediction algorithms. This means that k-NNbsl implicitly takes the idea of clones into account, and thus a form of analogical reasoning. Differences and resemblances of these two approaches are discussed in the next section.

D. Experiments and discussion

We evaluated the performance of the aforementioned algorithms in terms of MAE and RMSE on two datasets, the movielens-100K and movielens-1M datasets 1 , containing 100, 000 and 1M ratings respectively. Results are shown in tables I and II and where calculated using 5-folds crossvalidation. For each of these algorithms, the number of neighbors or clones used to output a prediction is k = 40, except for the bruteforce algorithm where the number of clones can not be controlled. It is very clear that even a very straightforward approach of the clone-based recommendation principle significantly outperforms the most basic k-NN algorithm. It is however a lot heavier to compute, thus not very suitable for real world 1 http://grouplens.org/datasets/movielens recommendation purposes (its performances on the Movielens-1M dataset simply could not be computed). The two other clone-based algorithms however, have the exact same complexity of any k-NN-based algorithm which is a significant improvement from the algorithm described in section III-B. Surprisingly enough, out of the two Clone algorithms, it is the one that does not care about clones in its similarity measure that achieves the best results. This might be due to the fact that in the neighborhood based on MSD, µ uv is necessarily small and thus easier to estimate in a statistical significant way.

Performances of the Clone algorithms are close to those of the state of the art k-NNbsl algorithm. It is however important to understand that these algorithms differ on the following points:

• The Clone algorithms do not address item bias, which is a significant drawback. It may not be unreasonable to believe that incorporating item bias in the prediction would lead to better results. • There is a subtle yet meaningful difference of interpretation between the biases induced by both algorithms. In the clone algorithm, biases are all pairwise, meaning that they involve two users, and they are computed on items that both users have rated. As for the k-NNbsl algorithm, there is no such thing as a pairwise bias. Bias for a given user is computed using only its own ratings, and is a result of a global optimization problem involving the global mean of all ratings, which means that every single rating in R has an impact on the bias. • On the biggest dataset (Movielens-1M), the k-NNbsl algorithm appears to achieve better accuracy than the other algorithms, while this is not the case for the small dataset. A possible explanation is that as baselines are computed on the whole training set, they tend to capture most of the noise when the training set gets bigger, thus improving accuracy compared to more heuristic-based approach. It should also be noted that in fact, it is recommended to perform a shrinkage on the similarity measure of algorithm k-NNbsl, in order to take into account the number of common items between two users: the more items they share, the more confident we are when computing their similarity [START_REF] Koren | Factor in the neighbors: Scalable and accurate collaborative filtering[END_REF]. Such an approach can improve significantly both RMSE and MAE of the algorithm. Similarly, in the clone-based approach, it might be of interest to discount clones that rely on a too small number of common items.

V. TOWARDS AN ORDINAL VIEW OF RATINGS

We may wonder if one can devise a counterpart of the numerical clone-based approach, which would be compatible with an ordinal view of the ratings. Indeed, an extreme way for unbiasing and comparing two sets of ratings is to forget about their numerical values, and only consider their rankings. The idea of viewing ratings in a ordinal manner has been advocated in [START_REF] Koren | Ordrec: An ordinal model for predicting personalized item rating distributions[END_REF]. In this section, we discuss an ordinal counterpart of the analogical approach previously presented. Analogical reasoning with ordinal data has first been proposed in [START_REF] Barbot | La proportion analogique dans les groupes. Applications à l'apprentissage et à la génération[END_REF], yet with a different concern.

A. An algorithm for rank prediction Indeed the idea that "the rating of user u for item i is to the rating of user v for item i as the rating of user u for item j is to the rating of user v for item j may be understood as well in an ordinal manner. This leads to state that "the relative ranking of item i among the ratings given by user u is to the relative ranking of item i among the ratings given by user v as the relative ranking of item j among the ratings given by user u is to the relative ranking of item j among the ratings given by user v.

This means that we need to compare the rankings given by two users u and v on their common items. In the following, ρ ui denotes the relative ranking of item i out of all the items rated by u. Our goal is to estimate all values of ρ ui , for any user and any item. The main steps of a possible algorithm is as follows:

1) Compute similarities between users, based on their rankings. A very popular similarity ranking measure is the Spearman's rank correlation coefficient, or Spearman's rho. 2) Compute an estimated rank ρui as an aggregation of all the rankings ρ vi extracted from the k nearest neighbors (using Spearman's rho as similarity):

ρui = v∈N k i (u) ρ vi • sim(u, v) v∈N k i (u) sim(u, v)
. This is obviously very similar to the neighborhood approach described in section IV-B, but instead of predicting a rating, we output a predicted rank. This approach is denoted as RankAnlg.

B. Experiments

We evaluated the performance of our algorithm and compared it to other previously described approaches, using the exact same evaluation protocol as in section IV-D. The Movielens-1m dataset was not benchmarked, as our algorithm is too computationally intensive.

RMSE and MAE are good measure for evaluation rating prediction accuracy, but are not suitable when it comes to evaluate rankings. A better measure is the Fraction of Concordant Pair, which evaluates the probability that given any two items i and j rated by any user u, the system has correctly estimated whether u prefers i over j or the inverse. To compute the FCP, we need to intermediate measures. c u defines the number of concordant pairs for user u, and d u its number of discordant pairs. The FCP is then computed over all users as the proportion of concordant pairs. Note that rui here may represent either a rating prediction or a ranking prediction ρui .

Results are reported in table III. Unfortunately, even a basic algorithm that was not designed for ranking prediction performs better in terms of FCP. To explain this difference, one may look at the distribution of average support over all the predictions, as shown on figure 2. Between two users u and v, the support is defined as the number of common items (|I uv |), which was used to compute the similarity between u and v. For a given prediction rui , the average support is the average of all the supports |I uv | over all users v ∈ N k i (u). The use Spearman's rho tends to provide with neighbors that have smaller support, thus leading to a less significant and less accurate estimation of the neighborhood, which may explain the differences in performance.

VI. CONCLUSION

This paper has provided a discussion on different ways for applying analogical reasoning to the prediction of ratings. After reporting a recent attempt where analogical proportions were built from 4-tuples of users, a computationally simpler approach is presented in this paper based on the idea that "the rating of user u for item i is to the rating of user v for item i as the rating of user u for item j is to the rating of user v for item j. This agrees with the transitive nature of the underlying analogical modeling. We have shown that this may apply to a quantitative view of ratings as well as to an ordinal view. Results obtained in the case of the quantitative view remain close to the ones of state-of-the art approaches, which can be retrospectively reinterpreted in an analogical way.

The idea behind the use of analogies is to go beyond the classical neighborhood to extract relevant information. However, this approach has a cost as it is more difficult to statistically validate the analogical link between users (or items). This is especially true in the ordinal case. Indeed, ordinal analogies tend to select users with a small common support, because it is easy to have the same ranking despite the fact this is not statistically relevant.

In the specific case of MovieLens dataset, a large majority of users seem to have a lot of close neighbors (in the classical sense) from which useful information can be extracted. In that case, examples for which analogical links bring more information than simple neighbors are quite rare. It should not come as a surprise that the pure analogical approach does not bring better results than standard approaches in this dataset.

The analogical approach might be advantageous in the case of low density dataset (i.e. when the set of close neighbors is small). In the same way, we might also think of combining the analogical approach with the classical one provided we are able to detect, for every prediction, which method is statistically the most relevant.

Formalizing analogical reasoning provides tools for extrapolation. This can be done in different ways as shown in this paper, depending on what basis we try to extrapolate. Another issue is to wonder about what we try to extrapolate. Thus, regarding recommendation, one might think of also using analogical reasoning to create configurations describing new items that may plausibly please users.

  ) T (a, b, a, b) (reflexivity) 2) T (a, b, c, d) =⇒ T (c, d, a, b) (symmetry) 3) T (a, b, c, d) =⇒ T (a, c, b, d) (central permutation) There are various models of analogical proportions, depending on the target domain. When the underlying domain is fixed, T (a, b, c, d) is simply denoted a : b :: c : d. Standard examples are: • Domain R: a : b :: c : d iff a -b = c -d iff a + d = b + c (arithmetic proportion) • Domain R n : a : b :: c : d iff a -b = c -d. This is just the extension of arithmetic proportion to real vectors. In that case, the 4 vectors a, b, c, d build up a parallelogram. • Boolean domain B = {0, 1}: a : b :: c : d iff (a ∧ d ≡ b ∧ c) ∧ (a ∨ d ≡ b ∨ c)

Fig. 1 .

 1 Fig. 1. Bob is a perfect clone of Alice.

  c u = {(i, j) ∈ I 2 s.t. rui > ruj and r ui > r uj } d u = {(i, j) ∈ I 2 s.t. rui ≥ ruj and r ui < r uj }

Fig. 2 .

 2 Fig. 2. Distribution of average support.

  of candidate ratings for all users v ∈ U i do for all t do if v ∈ t-Clones(u) then C ← C ∪ {r vi + t} // add x as a candidate rating

	end if
	end for
	end for
	rui = aggr
	x∈C


O Ben Ammar
email: benammar@univ-tlse2.fr

R Guillaume
email: romain.guillaume@irit.fr

C Thierry
email: thierry@univ-tlse2.fr

MRP parameter evaluation under fuzzy lead times

Keywords: Uncertainty, Fuzzy number, MRP, Lead-time

One of the main problems in supply chains is the supply planning of an actor (customer) in function of others network actors (suppliers). In this context, the knowledge of the supplier lead times ess. In this article we are particularly interested in the management of risks by an actor responsible of assembly activity. We suppose that each supplier is able to give his uncertain lead time by the meaning of intervals. In this collaborative context, we search to determine robust assembly process. In this study, we treat the case of a single-product and regular launches of the assembly. For this, we will propose a method based on MIP formulation and relaxation constraints approach to determine robust optimal both risk of assembly delay and storage of components.

INTRODUCTION AND RELATED WORKS

Faced to uncertainty, supply chains have implemented processes to mitigate risks. Planners plan their production using uncertain data as procurement plan (from customer to suppliers), lead times (from suppliers to customer).

An important factor of uncertainty is the difference between suppliers planned lead times (information flow) and suppliers real lead times (material flow). Indeed, this lead time is often uncertain and variable and it depends on several constraints: transportation time, prices, machine breakdowns, capacity constraints.

Several works in the literature [START_REF] Tang | Identifying risk issues and research advancements in supply chain risk management[END_REF][START_REF] Koh | Uncertainty under MRPplanned manufacture: review and categorization[END_REF], Guide and Srivasta, 2000) review identify risks in supply chain and proposed several techniques to establish a s risk management process.

Logistics, demand volatility, supply product-monitoring, supplier selection, quality and price are identified and classified by Tand and Musa (2011) as potential risks in a supply chain. Another classification is done by [START_REF] Wazed | Uncertainty factors in real manufacturing environment[END_REF] which consider demand, capacity and lead time uncertainties as the largest factors of risks in a manufacturing environment.

appear to be insufficiently studied favouring identifying risks issues as demand volatility, quality, excess inventory (Tand and Musa, 2011). Safety stocks, safety lead times and other measures are used by planners to control uncertainties in supply and demand [START_REF] Van Kampen | Safety stock or safety lead time: coping with unreliability in demand and supply[END_REF].

In the field of MRP (Material Requirement Planning), [START_REF] Dolgui | A State of the Art on Supply Planning and Inventory Control under Lead Time Uncertainty[END_REF], [START_REF] Damand | Paramétrage de la méthode MRP en environnement incertain: une revue de la littérature[END_REF] and [START_REF] Dolgui | Supply planning under uncertainties in MRP environments: A state of the art[END_REF] had studied the MRP parameterization under risks and classified the important techniques to reduce it. Several works made clear that safety lead times are a main parameter to cope the variability of suppliers lead time. [START_REF] Dolgui | Supply planning for single-level assembly system with stochastic component delivery times and service level constraint[END_REF] are considered two-level assembly systems with random component procurement times. They concluded that in the literature, the demand variability seems to be more studied than the lead time uncertainties.

Recently, Ben Ammar et al. (2013a[START_REF] Ammar | Optimization for supply planning in multilevel assembly systems with stochastic lead times[END_REF][START_REF] Ammar | Optimization approaches for multi-level assembly systems under stochastic lead times. Chapter in Metaheuristics for production systems[END_REF] have study the case under stochastic lead times. Nevertheless, in some cases, it seems be difficult to access to the probability distribution of the lead time.

The possibility distribution is often used to model uncertainty in the domain of supply chain management [START_REF] Peidro | Fuzzy optimization for supply chain planning under supply, demand and process uncertainties[END_REF][START_REF] Díaz-Madroñero | Fuzzy goal programming for material requirements planning under uncertainty and integrity conditions[END_REF]. In this paper we propose to model the uncertainty of the lead time using possibility distribution (Dubois and Prade, 2006) since this model requires less information than probability distribution (only the mode, the maximal and minimal value of the lead time).

To deal with the possibility distribution we can distinguish several different approaches. The first one consists in using a function aiming at ranking fuzzy numbers in order to allow the decision maker to defuzzify imprecise values. [START_REF] Peidro | Fuzzy optimization for supply chain planning under supply, demand and process uncertainties[END_REF], [START_REF] Liang | Fuzzy multi-objective production/ distribution planning decisions with multiproduct and multi-time period in a supply chain[END_REF] and [START_REF] Liang | Application of fuzzy sets to manufacturing/distribution planning decisions with multiproduct and multi-time period in supply chains[END_REF] apply this approach for uncertainty on demand quantity. After the defuzzification process, the result is a classical linear optimization system.

A second approach, based on the fact that a possibility distribution can be seen as a set of probability distributions, consists in choosing one of those probability distributions, according to the attitude of the decision maker (e.g. pessimistic using necessities, optimistic through possibilities, etc.). [START_REF] Gao | Fuzzy Minimum-Risk Material Procurement Planning Problem[END_REF] apply this approach on demand uncertainty. Once this choice has been made, it is possible to use a stochastic optimization model. So, the decision maker chooses for which probability distribution his solution will be optimal.

A third approach is possibilistic optimization, which tries to find the solution which minimizes the cost and maximizes the possibility level of a considered scenario. In other terms, this approach finds a "possibly optimal" solution; the level of possibility that the considered scenario will happen is therefore maximal. [START_REF] Mula | Material Requirement Planning with fuzzy constraints and fuzzy coefficients[END_REF] apply this approach for fuzzy constraints and demand quantity.

The fourth approach is The objective is to minimize the necessity level that a cost function is greater than a given level. This approach has been applied to the case of periodic demand uncertainty [START_REF] Guillaume | A robust lot sizing problem with ill-known demands[END_REF]) and cumulative demand uncertainty (Guillaume et al.2013). But under our knowledge, this approach does not have been applied to the lead-time uncertainty.

Another one is to propose a decision support approach which consists in showing all possible solutions due to the uncertainty. In other worlds, it propagates the uncertainty thought the MRP and computes all possible released quantities. This approach has been developed firstly for MRP under uncertainty on quantity of demand [START_REF] Grabot | Integration of uncertain and imprecise orders in the MRP method[END_REF].

Then it has been generalized to take into account the uncertainty on the date of the demand (Guillaume et al. 2011a) on quantity and finally has been applied for uncertain lead time (Guillaume et al. 2011b).

In this paper, the main target is to help the decision maker to choose a solution under uncertainty and not to compute one. The question is how to determine the planned lead time parameter in function of uncertainties and of the variability of the real lead time.

To apply the fourth approach aforementioned, the first step involves computing the possibility distributions of cost under uncertainty on lead-time. The case of a single product and regular launches of the assembly are considered. The final product is assembled using several types of components. Each type of components is delivered by a given supplier. by the supplier and the customer and varies in a fuzzy interval.

The rest of paper is organized into five sections. In section 2, the problem is described and the background is presented. Section 3 shows how the maximal-minimal fuzzy costs are estimated. The introduced method is illustrated with a numerical example in section 4. At the conclusion of the study (section 5), some future perspectives are detailed.

PRESENTATION OF THE PROBLEM AND BACKGROUND

In this section, the considered problem and the related background on MRP and uncertainty models are presented.

Description of the considered problem

In this paper, we suppose that the customer orders components from suppliers. The MRP perform depends on the parametrization of the suppliers planned lead times which determines the level of inventory or the level of backordering. However, the lead times of some components depend on suppliers and its uncertainty could increase instability in the supply chain.

In addition, we suppose that it seems to be difficult for the supplier to know the real lead time with precision.

Nevertheless, the supplier has knowledge of the lead time uncertainty which can be shared with the customer.

In this context, the main idea is to help the customer planners to choose the appropriate planned lead times of the MRP which minimize the risks of both backordering of the final product and inventory of components. In this study the demand of the final product is supposed constant and known.

So, in this paper a method is proposed to help planners to parametrize the lead times of suppliers under some hypothesis. More precisely, we suppose that:

-A given component is only used for a final product and does not appear at several levels of the bill of materials -The demand is constant and known over the horizon -The component inventory is always preferred to the product inventory (added value in the assembly process)

Fig. 1. The bill of materials where the final product and the components 1 are produced by the customer and the components 2, 3 and 4 by different suppliers.

Material Requirement Planning (MRP)

In supply chains, each actor uses the MRP process to compute both production and procurement plans. In this section, we present a linear model of MRP. Nevertheless, a set of other possible formulations of this problem exists. For example it depends on the planning rules, set up cost or capacity constraints. The presented model uses an unlimited capacity and a Lot-for Lot policy. Component 3 (purchased)

The maximal and minimal cost over all possible scenarios of lead time can be formulated as an optimization problem with respectively the objective ( 7) and ( 8):

(7)

(8) This modification affects the constraints of the MRP model (the first 6 equations) by taking into account the difference between the planned lead time and the real lead time .

Let the following variables:

Dependent variables:

: quantity of product which can be assembled at period : quantity of product which arrives at period and which has been released at period : quantity of component which arrives at period : quantity of product which is really assembled at period Decision variables:

: planned production of component at the period The constraints become:

(9) (10) (11) (12) (13) (14) (15) (16) (17)
This formulation is not computable since decision variables are indexed. In the next section, we propose a mixed integer formulation of both maximization and minimization of cost problems under uncertain lead time.

Evaluation of maximal and minimal cost under uncertain lead time

Firstly we will show that under the hypothesis of known and constant demand, we can consider only the single period problem. Since, the best and the worst case for each demand of the horizon is the same. For the best case it is trivial, since the less costly lead time cannot be inflated by the previous or the next period. For the worst case we have two cases, if the worst case is to be late for a given period, this worst case will be the same for all periods; and if all components are late there are no compensation between previous and next periods. Otherwise, if the worst case is to be early for the demand it is the same reasoning.

To take off the lead time in the index of constraints (4) and (5), three decisions variables are introduced:

: variable which indicates where we are in the interval of lead time (0 means lower bound and 1 upper bound) of component : the date of availability of component : the real date of assembly of product

We add two parameters: : the number of component required to satisfy the demand : the planned date to order the component Now, the objective function does not depend on planning horizon. It can be expressed as:

Or (18)
The constraints are: Precedence constraints:

(19)
Ready dates constraints: a product , cannot be assembled before its planned date:

(20) (21)
Inventory constraints for components:

(22) (23)
Backordering constraint for the final products:

(24)
Backordering constraint of final product for the horizon:

(25)

In the case of minimization, the function max of constraints ( 19) and ( 20) can be easy linearized using relation:

(26) (27) (28)
Unfortunately for the maximization problem, we need to add binary decision variables to linearize the constraints ( 19) and (20).

So the constraints (19) can be reformulated using 3 constraints (29), ( 30) and (31). Let a big value and a binary variable thus that if the maximum is reached for the component zero otherwise:

(29) (30) (31)
In the same way the constraints (20) can be reformulated using 3 constraints (32, 33 and 34) and two binaries variables and :

(32)

(34)

NUMERICAL EXAMPLE

In this example, we consider the bill of material presented in figure 2. The demand of final product is equal to 100 for the date 12.

The lead time of components 2, 3 and 4 are uncertain:

For component 2, it is triangular fuzzy interval:

For component 3, it is trapezoidal fuzzy interval:

For component 4, it is triangular fuzzy interval:

The lead times of the final product and the component 4 are the crisp value 1. The backlogging cost for the final product is equal to 50. The inventory costs for components are: , , . The Decision Maker wants to evaluate the impact of uncertainty of two possible parametrizations of lead times: , and or . So, , for the first parametrization and for the second one. The possible distributions of possible cost are represented in Fig. 3. The second one seems to be best for the most possible values. Nevertheless, for the first parametrization is better than the second one for the upper bound. Both parameterizations are equivalent for the lower bound for .

In conclusion, the first parametrization is most robust and less subject to uncertainty than the second one.

CONCLUSION AND PERSPECTIVES

In this paper, we are interested in a supply chain where the customer orders components from suppliers. However, the lead times of some components depend on suppliers and could increase instability in the supply chain. In other words, in the case of lead time uncertainty the MRP performance of suppliers planned lead times to parameterize the level of inventory or the level of backordering.

In addition, we supposed that it seems to be difficult for the supplier to know the real lead time with precision. Nevertheless, the supplier has knowledge of the lead time uncertainty which is shared with the customer. In this context, the main idea is to help the customer planners to choose the appropriate planned lead times of the MRP which minimize the risks of both backordering of the final product and inventory of components. In this study the demand of the final product is supposed constant and known.

Our future work will focus on the parameterization of the MRP system under uncertain lead times, limited capacity and variable demand. The main objective will be to parameterize MRP system under several uncertainties as lead times, demand and capacity.

Fig. 3 .

 3 Fig. 3. Representation of possibility distribution of cost for two possible parametrization.

the set of final products and the set of components (produced or supplied). Backordering cost for the final products ( and inventory holding costs for components ( ) are considered. Only the external demand for the final product is introduced.

Let the following parameters:

: the demand of final product , for the period : the planned lead time of product : the quantity of component required to produce one product : cost of handing the component : cost of backordering the final product

Let the following variables: Decision variables: : the production (or supply) quantity of product , for the period Dependent variables:

: inventory of component , at the end of the period : backordering of final product , at the end of the period In this context the objective function is to minimize the cost which is the sum of the inventory holding costs for components and the backlogging costs for the final products under constraint:

(1) With:

Production constraints

(2)

Material flow constraints for the final products

(3)

Backordering constraints for the final products (4)

Material flow constraints for the components

Inventory constraints for components (the demand is the requirement at the period of the next product of the bill of material):

(6)

Model of

In this paper we suppose that the lead time shared by the supplier to the customer is known with uncertainty (since it depends on the capacity and demand of supplier). We propose here that the supplier sends a fuzzy lead time to the customer. So this lead time is modelled by fuzzy intervals:

(see Fig. 2), where is the lower value of the lead time for the possibility of component and the uncertainty of the lead time for the possibility . If possibility of a value is 1, it means that it is the most possible value of lead time. Otherwise, if the possibility of this value is 0, it means that it is an impossible value of lead time. A trapezoidal possibility distribution can be built by decision maker by giving the smallest interval in which he/she thinks the value of lead time will be.

Fig. 2. Representation of a trapezoidal fuzzy interval.

ESTIMATION OF MAXIMAL FUZZY COST OF A LEAD TIME PARAMETRIZATION

In this section, we present the formulation of the problem to estimate the maximal and the minimal possible impacts of lead time uncertainty on different costs. First we solve the problem for a given value of , so this problem is a problem under classical intervals . Then, it is possible to obtain both maximal and minimal possible costs for a possibility degree . Hence, to build the possibility distribution of cost for a given lead time, we need to solve the interval problem for a set of with the estimation step.

Formulation of problems

the real lead time of product released at period . More over a product is assembled from components , themselves are produced or are ordered from suppliers In the same way, is the final product or the component which needs the component c.

Possibility

Lead-time


Sylvie Doutre
email: doutre@irit.fr

Faustine Maffre

Peter Mcburney

A Dynamic Logic Framework for Abstract Argumentation: Adding and Removing Arguments

A dynamic framework, based on the Dynamic Logic of Propositional Assignments (DL-PA), has recently been proposed for Dung's abstract argument system. This framework allows the addition and the removal of attacks, and the modification of the acceptance status of arguments. We here extend this framework in order to capture the addition and the removal of arguments. We then apply the framework on an access control case, where an agent engages in an argued dialogue to access some information controlled by another agent.

Introduction

In Dung's approach to argumentation [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], an argument system is represented as a set of (abstract) arguments and a binary attack relation between these arguments. Several semantics-ways to evaluate which arguments should be accepted-have been developed from this model (see [START_REF] Baroni | Semantics of abstract argument systems[END_REF]), some of them referred as "extension-based". These are semantics which define acceptable sets of arguments, called extensions.

Logical representations of Dung's approach of argumentation have been presented, based for instance on propositional logic [START_REF] Besnard | Checking the acceptability of a set of arguments[END_REF], or more recently on dynamic logic [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]. In these contributions, the argument system is described by a boolean formula and each type of semantics is also represented by a boolean formula; for a given semantics, any interpretation of the propositional variables for which both formulas are true characterizes an extension. In [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], the use of a dynamic logic (DL-PA-Dynamic Logic of Propositional Assignments [START_REF] Balbiani | Dynamic logic of propositional assignments: a wellbehaved variant of PDL[END_REF]) furthermore allows us to model updates of the argument system, such as addition or removal of an attack, or modification of extensions. [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] is not the only approach which has tackled the question of the dynamics of argument systems (see [START_REF] Coste-Marquis | On the revision of argumentation systems: minimal change of arguments statuses[END_REF][START_REF] De Saint-Cyr | Argumentation update in YALLA (yet another logic language for argumentation)[END_REF] for instance), but this one provides a single framework which encompasses at the same time the argument system, the logical definition of the change to enforce, and the change operations to perform. Moreover, the logic it is based on is non-specific to argumentation since it has already been applied in various contexts [START_REF] Gaudou | How to do social simulation in logic: modelling the segregation game in a dynamic logic of assignments[END_REF][START_REF] Maffre | Ignorance is bliss: observability-based dynamic epistemic logics and their applications[END_REF].

Following an idea that was triggered in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], we extend [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]'s framework to capture addition and removal of arguments. An extension of Dung's system is proposed to take into account, within the set of arguments, those which are currently considered, or, say, enabled. The formulas that describe the argument system and the semantics are modified to take into account this new notion of enabled arguments. We illustrate our contribution with an example from [START_REF] Perrussel | A persuasion dialog for gaining access to information[END_REF], in which the authors present a protocol for agents engaging in an argued dialogue to access some information.

The paper is organized as follows. In the next section we introduce the example of access control dialogue that we will use throughout the paper. In Sect. 3 we show how to extend the framework of [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] to capture addition and removal of arguments. In Sect. 4 we show how this extension can be used to formalize updates of the argument system during the dialogue. Section 5 concludes.

Our Running Example

In this example taken from [START_REF] Perrussel | A persuasion dialog for gaining access to information[END_REF], an agent, called the client (here, Brussels agent), wants to access some information. He engages a dialogue with the agent controlling it-the server (London agent)-in order to convince him to grant authorization to access this information. The second agent explains the reasons why he cannot give this access by presenting all the arguments attacking the client's arguments that he knows.

"Robert is a British businessman visiting Brussels for a meeting. During his visit he becomes ill and is taken unconscious into hospital. The staff of the hospital suspect Robert has had a heart attack and seek to prescribe appropriate drugs for his condition. Unfortunately the safe choice of drugs depends upon various factors, including prior medical conditions that Robert might have and other drugs he may be taking. The hospital's agent is given the goal of finding out the required information about Robert, from the agent representing his London doctor.

In order to gain access to information about Robert, the agent of Brussels Hospital (B. agent) establishes the following dialogue with the London agent (L. agent): 0. B. agent: I would like to dialog with the agent of Robert's British doctor; I request Robert's health record. 1. L. agent: I cannot provide you Robert's health record because Robert has only given his British doctor limited consent to pass on his personal information (argument a 1 ).

B. agent:

This record could possibly include information that could affect the treatment of Robert's heart failure. I request it, Robert's life may be at stake (argument a 2 )! 3. L. agent: I cannot divulge this information, because British law prohibits passing on information without the consent of the provider of the information (argument a 3 ). 4. B. agent: EC law takes precedence over British law when it would be in the interests of the owner to divulge the information (argument a 4 ). You should allow me to access the record. 5. L. agent: Only Robert could decide what would be in his interests (argument a 5 ). 6. B. agent: Robert's doctor owes a duty of care to Robert and, should he die, the doctor might be sued by his family, or the Brussels hospital, or both (argument a 6 ). 7. L. agent: OK. I provide you the requested record: Robert's history of diabetes is..." Some arguments are directly in favor of giving the permission to access the information (a 2 and a 6 ), some are directly against this permission (a 1 and a 3 ), while others are not directly linked to the permission (a 4 and a 5 ) but contradict other arguments. The dialogue ends after London agent has implicitly considered acceptable Brussels' final argument (a 6 ), which supports the permission to give the requested information to Brussels. No such argument was acceptable for London agent earlier in the dialogue.

In this paper, we focus on capturing the evolution of the acceptability of arguments for London agent, after each addition of argument. This can be seen as an a posteriori analysis of the dialogue, that allows us to understand the reasons why the permission to access the information was first refused, and then given.

Representing Argument Systems

We extend here the definition of an argument system, and of its logical formalization [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]. We present DL-PA logic and how to compute extensions with DL-PA programs.

Logical Representation of an Argument System

Argument System. In order to capture addition and removal of arguments, we add a component to Dung's argument system [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]: the set of currently considered ("enabled") arguments, among all the arguments of the system. These arguments are those which are known, at some step, in the context of a dialogue. A contains all possible arguments that may arise during the dialogue, while A En constitutes the set of arguments that have been uttered until now.

An argument system for enablement is represented by a directed graph whose nodes are enabled arguments and edges are attacks between enabled arguments: there is an edge between a and b if (a, b) ∈ R, a ∈ A En and b ∈ A En . Hence the representation contains less information than the original model. Note that as soon as an argument is enabled, all its attacks from (resp. to) other arguments are considered. When A En = A, the argument system for enablement comes down to Dung's argument system.

Example 1. In our running example, six arguments were presented during the dialogue: A = {a 1 , a 2 , a 3 , a 4 , a 5 , a 6 }. Let us write F i = (A, A En i , R) the argument system at step i (steps are numbered as in Sect. 2, from 0 to 6). The attack relation, from the point of view of London agent, and according to [START_REF] Perrussel | A persuasion dialog for gaining access to information[END_REF], is R = {(a 1 , a 2 ), (a 3 , a 2 ), (a 4 , a 3 ), (a 5 , a 4 ), (a 6 , a 1 ), (a 6 , a 3 )}.

At step 0, no argument is considered:

A En 0 = ∅. Then, a 1 is uttered: A En 1 = {a 1 }.
This argument is not attacked nor attacks any enabled argument; the graph that represents the argument system thus is:

a 1 Then a 2 is presented (A En 2 = {a 1 , a 2 }
) and the graph becomes:

a 1 ✲ a 2
The dialogue goes on until all arguments are presented:

a 1 ✲ a 2 ✛ a 3 ✛ a 4 ✛ a 5 a 6 ❅ ❅ ■ ✒
The set of enabled arguments A En 6 is then equal to A.

In order to logically represent an argument system for enablement F, we extend the language of [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]. As in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], a set of attack variables is used to represent attacks:

ATT A = {Att a,b : (a, b) ∈ A × A}.
Att a,b means that a attacks b. We consider in addition a set of enablement variables:

EN A = {En a : a ∈ A},
where En a means that a is enabled (or "considered").

Let L Att,En be the set of all formulas that are built variables from ATT A ∪ EN A . The theory describing the framework F = (A, A En , R) is the following boolean formula:

Th F = (a,b)∈R Att a,b ∧ (a,b) R ¬Att a,b ∧ a∈A En En a ∧ a A En ¬En a
Note that in the theory, Att a,b is true even if a or b are not enabled. This is required to not loose any information, and will be important for updates (see Sect. 4).

Example 2. We have 6 arguments in our running example. This means that ATT A contains 36 variables and EN A contains 6 variables. Therefore, whatever the step i of the dialogue, Th F i is a conjunction of 42 literals. For simplification, we do not write explicitly every attack literal As examples, the theory at step 0 is:

Th F 0 = (a,b)∈R Att a,b ∧ (a,b) R ¬Att a,b ∧¬En a 1 ∧¬En a 2 ∧¬En a 3 ∧¬En a 4 ∧¬En a 5 ∧¬En a 6
and the theory at step 3 is:

Th F 3 = (a,b)∈R Att a,b ∧ (a,b) R ¬Att a,b ∧ En a 1 ∧ En a 2 ∧ En a 3 ∧ ¬En a 4 ∧ ¬En a 5 ∧ ¬En a 6
Argumentation Semantics. Given an argument system, an acceptability semantics identifies a set of extensions, i.e., acceptable sets of arguments. There may be none, one or several extensions. As in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], we characterize extensions thanks to a set of acceptability variables:

IN A = {In a : a ∈ A}
where In a stands for "argument a is in the extension". Without the notion of enabled arguments (that is, when all arguments are always considered), it has already been shown how to encode the stable, admissible and complete semantics with propositional formulas [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]. These definitions can be adapted to consider enabled arguments only. In this case, extensions are subsets of A En and only attacks between arguments from A En are considered. In the corresponding formulas, we only include an argument if it is enabled. Also, attacks must be considered only if they link enabled arguments. To this end, we define the following formula:

Att En a,b = Att a,b ∧ En a ∧ En b . Now
we can easily transform formulas from [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]: we check if the argument is enabled, otherwise it will not be included in the extension, and we replace attacks variables Att a,b by formulas Att En a,b to ensure they are indeed present. We illustrate this transformation to capture the stable semantics. Let L Att , ,En,In be the language of formulas built from

P = ATT A ∪ EN A ∪ IN A . Definition 2. Let F = (A, A En , R) be an argument system for enablement. Let S ⊆ A En be a set of enabled arguments. S is conflict-free if ∀a, b ∈ S , (a, b) R. S is a stable extension if S is conflict-free and ∀b ∈ A En \S , ∃a ∈ S such that (a, b) ∈ R

(any considered argument outside the extension is attacked by at least one in the extension).

Note that we do not need to restrict R to the set of considered arguments as a and b both belong to S which is a subset of A En .

The following formula captures the stable semantics 1 : programs can express that some property holds after the modification of the current valuation by the program. In our case, they will allow us to update the theory associated to the argument system as the dialogue progresses. We will see that the results from [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] are still applicable in our framework. Hence we also consider the star-free version of DL-PA [START_REF] Herzig | A dynamic logic of normative systems[END_REF] with the converse operator.

Stable A = a∈A En a → In a ↔ ¬ b∈A (In b ∧ Att En b,a ) ∧ ¬En a →
Language. The language DL-PA is defined by the following grammar:

π p←⊤ | p←⊥ | ϕ? | π; π | π ∪ π | π - ϕ p | ¬ϕ | ϕ ∨ ϕ | π ϕ
where p ranges over P. The formula π ϕ reads "after some execution of the program π formula ϕ holds". The formula [π]ϕ, abbreviating ¬ π ¬ϕ, reads "after every execution of the program π formula ϕ holds". The atomic programs p←⊤ and p←⊥ respectively make p true and make p false. The operators of sequential composition (";"), nondeterministic composition ("∪") and test ("(.)?") are from PDL. The operator "(.) -" is the converse operator: the formula π -ϕ reads "before some execution of the program π formula ϕ was true". Other boolean operators are abbreviated as usual. Like in PDL, skip abbreviates ⊤? ("nothing happens").

Semantics and Validity.

Models of DL-PA formulas are subsets of the set of propositional variables P, i.e., valuations. DL-PA programs are interpreted by means of a relation between valuations. Atomic programs p←⊤ and p←⊥ are interpreted as update operations on valuations, and complex programs are interpreted just as in PDL by mutual recursion. Table 1 gives the interpretation of the DL-PA connectives.

Two formulas ϕ 1 and ϕ 2 are formula equivalent if ||ϕ 1 || = ||ϕ 2 ||. Two programs π 1 and π 2 are program equivalent if ||π 1 || = ||π 2 ||. In that case we write π 1 ≡ π 2 . An expression is a formula or a program; equivalence is preserved under replacement of a sub-expression by an equivalent expression [START_REF] Balbiani | Dynamic logic of propositional assignments: a wellbehaved variant of PDL[END_REF]. A formula ϕ is DL-PA valid if it is true in all valuations, i.e., if ||ϕ|| = 2 P .

Constructing Extensions with DL-PA

As in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], we can build extensions of an argument system by means of DL-PA programs. We recall the program vary(P), from [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], with P = {p 1 , . . . , p n } a set of variables:

vary(P) = (p 1 ←⊤ ∪ p 1 ←⊥); . . . ; (p n ←⊤ ∪ p n ←⊥)
vary(P) is a sequence of subprograms, each step i of the sequence nondeterminiscally setting the value of p i to true or to false. (Note that the ordering of the p i does not matter.) Executing vary(P) from a valuation v will lead to any valuation where variables from P\P have the same value than in v, while variables from P can have any value.

Given an argument system F, the idea of [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] is to start from a valuation where the theory Th F is verified, and vary accessibility variables In a ; this leads to several valuations, some corresponding to an extension. To "filter" these valuations to keep stable extensions only, we test the formula capturing the semantics (see Sect. 3.1). More formally, we use the following program to build stable extensions:

makeExt Stable A = vary(IN A ); Stable A ?
Example 4. In Example 3, we have seen that v {a 1 ,a 3 } = v Th ∪ {In a 1 , In a 3 } is the only stable extension. Th F 3 is true in this valuation thanks to v Th , and the values of the accessibility variables describe the extension. Executing makeExt Stable A from, e.g., v Th , will lead exactly to v {a 1 ,a 3 } ; Stable A is not true for any other valuation linked by vary(IN A ).

The following results are adapted from [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF].

Lemma 1. Let F be an argument system for enablement. Let v 1 be a model of Th

F . Then (v 1 , v 2 ) ∈ ||makeExt Stable A || if and only if v 2 is a model of Th F ∧ Stable A .
The main result about the construction of extensions with DL-PA is as follows.

Proposition 2. Let F = (A, A En , R) be an argument system for enablement. The following equivalence is DL-PA valid:

Th F ∧ Stable A ↔ (makeExt Stable A ) -Th F
Remember that π -ϕ means "before some execution of the program π formula ϕ was true". This indeed corresponds to the update of Th F by makeExt Stable A .

With the extended framework, we are now able to model changes that may happen in a dialogue, that is, addition, and possibly, removal of arguments. We update the theory corresponding to an argument system to this end:

Th F ⋄ En a = (En a ←⊤) -Th F Th F ⋄ ¬En a = (En a ←⊥) -Th F
where Th F ⋄ En a refers to updating the system to add (enable) argument a and Th F ⋄ ¬En a to updating the system to remove (disable) argument a. Since attacks are already in the theory even if arguments are not considered, we do not need to include them in our update: all the attacks from (resp. to) a to (resp. from) other enabled arguments, are considered. The framework, being an extension of [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], however allows us to remove some of these attacks, or add extra ones, if necessary.

Example 5. In our running example, at step 0, A En 0 = ∅, and Th F 0 is as described in Example 2. At step 1, argument a 1 is enabled. The theory is thus updated as follows:

Th F 0 ⋄ En a 1 = (En a 1 ←⊤) -Th F 0
Using properties of DL-PA, we explain in details this update. First, it is shown in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] that (p←⊤) -is equivalent to p? ∪ (p?; p←⊥) (p is now true and was either already true or was false). Hence:

Th F 0 ⋄ En a 1 ≡ En a 1 ? ∪ (En a 1 ?; En a 1 ←⊥) Th F 0 DL-PA shares most properties about program operators with PDL [START_REF] Balbiani | Dynamic logic of propositional assignments: a wellbehaved variant of PDL[END_REF], such as:

π ∪ π ′ ϕ ↔ π ϕ ∨ π ′ ϕ π; π ′ ϕ ↔ π π ′ ϕ χ? ϕ ↔ χ ∧ ϕ
Using these, we can transform our updated theory:

Th F 0 ⋄ En a 1 ≡ (En a 1 ∧ Th F 0 ) ∨ (En a 1 ∧ En a 1 ←⊥ Th F 0 )
The first part of the disjunction is equivalent to ⊥ since Th F 0 is a conjunction of literals and one is ¬En a 1 . For the second part, we consider two properties of DL-PA [START_REF] Balbiani | Dynamic logic of propositional assignments: a wellbehaved variant of PDL[END_REF]:

p←⊤ (ϕ ∧ ϕ ′ ) ↔ p←⊤ ϕ ∧ p←⊤ ϕ ′ p←⊤ ¬ϕ ↔ ¬ p←⊤ ϕ
With these equivalences, we know that in En a 1 ←⊥ Th F 0 , the operator En a 1 ←⊥ can distribute over the conjunction and be placed before every literal of Th F 0 , and that for negative literals, En a 1 ←⊥ can be "pushed" against the variable. We obtain:

Th F 0 ⋄ En a 1 ≡ En a 1 ∧ (a,b)∈R En a 1 ←⊥ Att a,b ∧ (a,b) R ¬ En a 1 ←⊥ Att a,b ∧ ¬ En a 1 ←⊥ En a 1 ∧ ¬ En a 1 ←⊥ En a 2 ∧ ¬ En a 1 ←⊥ En a 3 ∧ ¬ En a 1 ←⊥ En a 4 ∧ ¬ En a 1 ←⊥ En a 5 ∧ ¬ En a 1 ←⊥ En a 6
We finally use a last DL-PA property [START_REF] Balbiani | Dynamic logic of propositional assignments: a wellbehaved variant of PDL[END_REF]:

p←⊥ q ↔        ⊥ if p = q q otherwise
Most of the conjuncts fall in the second category and thus are not affected by the program, except ¬ En a 1 ←⊥ En a 1 which is equivalent to ¬⊥, that is, to ⊤, and thus will disappear from the conjunction. We end with:

Th F 0 ⋄ En a 1 ≡ En a 1 ∧ (a,b)∈R Att a,b ∧ (a,b) R ¬Att a,b ∧ ¬En a 2 ∧ ¬En a 3 ∧ ¬En a 4 ∧ ¬En a 5 ∧ ¬En a 6
which is the theory Th F 1 , i.e., for A En 1 = {a 1 }. Example 6. We can finally fully run through our main example. A and R remain constant and are as described in Example 1. We are going to run the example from step 0 to step 6, hence showing the addition/enablement of arguments step after step. Notice that it may be run the other way round, from step 6 to step 0; the removal/disablement of arguments would then be illustrated.

At step 0, A En 0 = ∅, and Th F 0 is as in Example 2. The execution of (makeExt Stable A ) -Th F 0 allows one to get the only stable extension of F 0 : ∅. When a 1 is uttered, the set of enabled arguments becomes A En 1 = {a 1 }. As we have seen in Example 5:

Th F 1 = (En a 1 ←⊤) -Th F 0

Executing makeExt Stable

A from any valuation satisfying Th F 1 will lead to one valuation, where In a 1 is true and every In a i for i ∈ {2, . . . , 6} is false; this means we obtain one stable extension: {a 1 }.

We summarize the results at each step of the dialogue in Table 2. Numbers in the first column are steps. In the second column, we write, first, the DL-PA formula describing the updated theory, and second, the DL-PA formula true in valuations corresponding to (stable) extensions. Then in the third column we give the current graph representing the argument system, and the set of extensions.

After the server (London agent) has presented all his arguments, we end up with one extension: {a 2 , a 5 , a 6 }. In this setting, he accepts to provide the information as argument a 6 , which directly supports the permission, belongs to at least one extension (following the principle of trustfulness of [START_REF] Perrussel | A persuasion dialog for gaining access to information[END_REF]).

Conclusion

This paper presents an extension of the formal framework of [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF], which allows us to update the argument system by adding or removing an argument. We achieve this by Table 2. Evolution of the argument system and of the set of extensions during the dialogue including a set of currently enabled arguments to the argument system and a new set of propositional variables reflecting this set in the logical representation. With new appropriate formulas for the argument system and semantics, the formalization of [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] is general enough to transpose well to this extension. Our new framework allows us to easily model the evolution of the argument graph during dialogue, as shown with the example of [START_REF] Perrussel | A persuasion dialog for gaining access to information[END_REF]. It is interesting to note that while we focused on the stable semantics, any semantics that can be described by a logical formula can be encoded in our framework.

Implemented theorem proving methods for DL-PA have not yet been developed, DL-PA being quite recent, but a paper such as the present on applications motivates implementation work.

The evolution of the argument system and the set of extensions during the dialogue, as illustrated in Table 2, is similar to the key idea of Discourse Representation Theory (DRT) [START_REF] Kamp | From Discourse to Logic: Introduction to Modeltheoretic Semantics of Natural Language, Formal Logic and Discourse Representation Theory[END_REF] in linguistics. This idea is that the semantics of a dialogue may be constructed by the participants, jointly and incrementally as the dialogue proceeds. Other work in multi-agent systems has also drawn on these ideas, for example, [START_REF] Bratu | A software infrastructure for negotiation within inter-organisational alliances[END_REF][START_REF] Mcburney | Posit spaces: a performative theory of e-commerce[END_REF].

The dialogue analysis has been made from the point of view of one agent in this paper, and a posteriori. A perspective is to extend it to several agents, and to capture some ongoing strategy each one of them may have to fulfill own goals. In this case, agents may or may not agree on the set of arguments and on the set of attacks. For every of his arguments, an agent could compute the set of extensions for the current graph plus this argument, and thereby identify the argument that brings him closer to his personal goal. This is similar to the update of extensions in [START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF] but with a different approach (modifying arguments rather than attacks). We leave this to future work.

Definition 1 .

 1 An argument system for enablement is a tuple F = (A, A En , R) where A is a finite set of abstract arguments; A En ⊆ A is the set of enabled arguments, and R ⊆ A × A is the attack relation: (a, b) ∈ R means that a attacks b.

  Att a,b and ¬Att a,b (Att a 1 ,a 2 , Att a 3 ,a 2 , and ¬Att a 1 ,a 3 . . .) but we keep the expression (a,b)∈R Att a,b ∧ (a,b) R ¬Att a,b . Note that, since in our case the attack relation R is constant, this expression remains constant.

DL-PA: Dynamic Logic of Propositional Assignments Dynamic

  ATT A ∪ EN A ∪ IN A : the variables that are currently true. The set of all valuations is 2 P . Valuations are denoted by v, v ′ , v 1 , v 2 , etc. A given valuation determines the truth value of the boolean formulas of the language L Att , ,En,In in the usual way. For a formula ϕ, a valuation where ϕ is true is called a model of ϕ and the set of models of ϕ is denoted by ||ϕ||. A formula is propositionally valid if it is true in all valuations, i.e., if ||ϕ|| = 2 P . The following results are adapted from[START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF].En } ∪ {In a : a ∈ E}. E is a stable extension of F if and only if v E is a model of Th F ∧ Stable A . Let us consider F 3 = (A, A En 3 , R) with A and R as in Example 1 and A En 3 = {a 1 , a 2 , a 3 }. a 1 ✲ a 2 ✛ a 3 Let v Th = {Att a,b : (a, b) ∈ R} ∪ {En a 1 , En a 2 , En a 3 }. Note that the theory Th F 3 (see Example 2) is true in v Th . F 3 has only one stable extension: {a 1 , a 3 }. Hence v {a 1 ,a 3 } = v Th ∪ {In a 1 , In a 3 } is a model of Th F 3 ∧ Stable A . Logic of Propositional Assignments DL-PA [1, 10] is a variant of Propositional Dynamic Logic PDL [9], with operators for sequential and nondeterministic composition of programs, test and iteration (the Kleene star), but where atomic programs are assignments of truth values to propositional variables. Modal operators associated to

	Proposition 1. Let F = (A, A En , R) be an argument system for enablement. Let E ⊆ A En . Consider v 3.2

¬In a Extensions and Valuations. A valuation is a subset of the set of variables P = E = {Att a,b : (a, b) ∈ R} ∪ {En a : a ∈ A 1 An equivalent way to express these formulas would be to use the set of enabled arguments.

For example, to describe the stable extensions, we would write: Stable A,A En = a∈A En In a ↔ ¬ b∈A En (In b ∧ Att b,a ) ∧ a A En ¬In a . This highlights the fact that when all arguments are enabled, i.e., when A En = A, we indeed retrieve formulas presented in

[START_REF] Doutre | A dynamic logic framework for abstract argumentation[END_REF]

.

Example 3.

Table 1 .

 1 Interpretation of the DL-PA connectives

Acknowledgements. This work benefited from the support of the AMANDE project (ANR-13-BS02-0004) of the French National Research Agency (ANR).