Zacharias Voulgaris
email: zvoulgaris@gatech.edu

Chris Sconyers
email: csconyers@gatech.edu

A Novel Feature Selection Method for Fault Diagnosis

Keywords: feature selection, dimensionality reduction, fault diagnosis, classification

A new method for automated feature selection is introduced. The application domain of this technique is fault diagnosis, where robust features are needed for modeling the wear level and therefore diagnosing it accurately. A robust feature in this field is one that exhibits a strong correlation with the wear level. The proposed method aims at selecting such robust features, while at the same time ascertain that they are as weakly correlated to each other as possible. The results of this technique on the extracted features for a real-world problem appear to be promising. It is possible to make use of the proposed technique for other feature selection applications, with minor adjustments to the original algorithm.

Introduction

The extraction of features is a relatively manageable and straightforward process, especially in cases where there is abundance of data. Also, as there have been developed methods for automating this process, the feature set size increases dramatically (leading to what is commonly refer to as the curse of dimensionality). However, the often large number of features does not necessarily mean better results in one's analysis of the problem at hand. Many of the extracted features are usually redundant and even relatively weak. Since the fault diagnosis process, in order to be carried out effectively requires one or more robust features; it is essential that an efficient feature selection step is required and demands the researcher's attention. Fault diagnosis based on the selected feature is usually carried out after the stage of feature fusion, which involves taking the selected features and creating a superfeature by combining them. However, in this paper the selected features are used as they are, so that they can be evaluated through their diagnosis classification performance.

Feature selection has been tackled mainly as an optimization problem. The relevant research includes supervised, unsupervised and semi-supervised ways to select the optimum subset of features [START_REF] Liu | Computational Methods of Feature Selection[END_REF]. Yet, the general approaches to feature selection are twofold: either rank the features according to some evaluation metric and select the top k ones, or select a minimum subset of features that allows for good performance (i.e. the quality of the dataset, in terms of relevant information, does not deteriorate). [START_REF] Liu | Computational Methods of Feature Selection[END_REF]. Furthermore, the feature selection techniques, particularly in the fault diagnosis/prognosis domain, can be categorized in two broad groups: optimal and sub-optimal methods, the former including exhausting search and the Brand & Bound algorithm, while the latter using methods like sequential search, floating search, plus-L-minus-R search [START_REF] Liu | Machinery Fault Diagnostics Based on Fuzzy Measure and Fuzzy Integral Data Fusion Techniques[END_REF].

The rest of the paper is structured as follows. In section 2 the related work to feature selection methods is presented and briefly analyzed, after the evaluation criteria for the features at hand are defined. Based on the analysis of the feature selection methods, the necessity to adopt an alternative approach is pinpointed for the application at hand. This approach is described, on a theoretical level, in section 3. In the section that follows (4), the application of the proposed method is exhibited, using some real world data from a project the authors are involved in. The results of the relevant simulations are also presented in this section. Afterwards, a discussion of this research is carried out in section 5. Conclusions are drawn and avenues of future research based on this work are mentioned in the final section of this paper (6).

Evaluation Criteria and Related Work

There have been numerous attempts to solve the feature selection problem using various strategies for obtaining a robust reduced feature set. Although most of these approach are classification-oriented (including data mining) [START_REF] Motoda | Feature Extraction, Construction and Selection -A Data Mining Perspective[END_REF][START_REF] Theodoridis | Pattern Recognition[END_REF][START_REF] Voulgaris | Discernibility Concept in Classification Problems[END_REF], some are designed having a fault diagnosis/prognosis problem in mind [START_REF] Liu | Machinery Fault Diagnostics Based on Fuzzy Measure and Fuzzy Integral Data Fusion Techniques[END_REF][START_REF] Sun | Combining Bootstrap and Genetic Programming for Feature Discovery in Diesel Engine Diagnosis[END_REF][START_REF] Lee | An Architecture for a Diagnostic/Prognostic System with Rough Set Feature Selection and Diagnostic Decision Fusion Capabilities[END_REF][START_REF] Saxena | Optimum Feature Selection and Extraction for Fault Diagnosis and Prognosis[END_REF].

Although the basic principles are the same in these disciplines, as regards the feature selection problem, in the later case the evaluation of a feature is more complicated. Namely, a robust feature in fault diagnosis (and prognosis) is characterized not merely by good distinguishability (discernibility, class separability, etc.) but by a sense of monotonicity as well (the more monotonic in relation to wear level the better). As monotonicity can be modeled by taking the relationship between consecutive wear levels (classes) so that the feature values form a monotonic pattern, it can be thought of as ordered discernibility. So far, the most widely-used and academically acceptable measure of monotonicity is the correlation coefficient.

There are several methods for dimensionality reduction, which are not related to the problem at hand (e.g. PCA yielding a small number of features to express almost the same information through different combinations of the original features). The term feature selection which is used in this research denotes that a subset of the original features is used, thereby maintain many of the original dataset characteristics and yielding more meaningful features in the new feature set.

Classification-oriented methods for feature selection include, but are not limited to, vertical compactness of data, the relevance-based algorithm approach, statistics-based techniques, and Genetic Algorithms [START_REF] Motoda | Feature Extraction, Construction and Selection -A Data Mining Perspective[END_REF]. Alternative approaches in the same category of methods for feature selection include the Receiver Operating Characteristics curve approach and class separability measures, through certain searching techniques (which are usually suboptimal) [START_REF] Theodoridis | Pattern Recognition[END_REF]. As regards class separability measures, one of the authors of this paper has conducted a thorough research on one of them (which he coined with the term Discernibility) with applications in feature selection, among a number of other research topics in the field of classification [START_REF] Voulgaris | Discernibility Concept in Classification Problems[END_REF].

Feature selection for fault diagnosis/prognosis [START_REF] Vachtsevanos | Intelligent Fault Diagnosis and Prognosis for Engineering Systems[END_REF], though exhibiting similarity in the methods it employs, often makes use of alternative ways to tackle this problem. Namely, in [START_REF] Liu | Machinery Fault Diagnostics Based on Fuzzy Measure and Fuzzy Integral Data Fusion Techniques[END_REF] an enhanced version of the Brand & Bound algorithm is proposed and implemented. Also, the use of consistency as a measure of feature evaluation for feature selection has been successfully employed, as it exhibits monotonicity and speed [START_REF] Liu | Machinery Fault Diagnostics Based on Fuzzy Measure and Fuzzy Integral Data Fusion Techniques[END_REF]. A Genetic Programming based approach has also been applied for feature selection, as it yields good results without the need for large samples, nor assumptions used in e.g. statistical approaches to the problem at hand [START_REF] Sun | Combining Bootstrap and Genetic Programming for Feature Discovery in Diesel Engine Diagnosis[END_REF]. Also, this approach is preferred by some researches due to its efficiency since it bypasses the analytical way of creating all possible feature subsets, which is an NP-hard problem [START_REF] Sun | Combining Bootstrap and Genetic Programming for Feature Discovery in Diesel Engine Diagnosis[END_REF]. Finally, a rough sets approach has also been employed for feature selection in this domain, with promising results [START_REF] Lee | An Architecture for a Diagnostic/Prognostic System with Rough Set Feature Selection and Diagnostic Decision Fusion Capabilities[END_REF].

It should be noted that feature selection is application dependent, especially in fault diagnosis/prognosis problems [START_REF] Saxena | Optimum Feature Selection and Extraction for Fault Diagnosis and Prognosis[END_REF]. Yet, there are some recurring patterns that are found across the different applications in the field. These are the basis for feature analysis and evaluation, and comprise of the following criteria [START_REF] Saxena | Optimum Feature Selection and Extraction for Fault Diagnosis and Prognosis[END_REF]: Distinguishability (often referred to as class separability or Discernibility), Detectability/isolatability, Identifiability, Degree of Certainty. The use of at least one of these criteria is essential for conducting a proper feature selection for the field of fault diagnosis/prognosis.

Note that most of the aforementioned methods for feature selection assume quantitative feature values. This is the most commonly encountered feature type in applications related to fault diagnosis. However, there exist several other feature types, which may require a different strategy for feature selection [START_REF] Pekalska | The Dissimilarity Representation for Pattern Recognition Foundations and Applications[END_REF].

Though all of the above methods show promising results in the applications they were tested, a generic and therefore versatile method of feature selection is yet to be found. The fact that feature selection often requires some type of threshold to filter out the redundant features is part of the problem. Another aspect of the problem is that the feature selection methods under consideration are based on one or, less often, more evaluation metrics that model the four criteria mentioned earlier. If the user of these methods wishes to experiment with alternative measures for ranking the features, this would be a time-consuming task which in some cases it is even infeasible, due to the nature of the feature selection method. An attempt to address these issues is made using an alternative, more generic approach to feature selection, which is presented in this paper.

Methodology

The proposed method performs feature selection in an efficient and automated way (which is why it is called Automated Feature Selector or AFS for short). AFS takes as inputs the feature matrix F (input values in classification terminology), the wear level vector W (target values) and, optionally, a correlation threshold th. The later is there in case the user wishes to obtain only features that meet a certain quality standard (e.g. strong correlation with the wear) and can be particularly useful in cases of very large feature sets.

The AFS method functions as follows. Initially, a dimensionality check is performed, to ensure that both F and W contain the same number of points (N). Once this is attained, the features are individually evaluated to determine how useful they are for the objective at hand. This is done by first calculating the correlation between each feature i (F i ) and W and storing it in a vector C. Then, the standardized Fischer Discriminant Ratio of Fi is calculated as well and stored in vector DR. By the term standardized we mean a variation of FDR such that it yields values in the interval (0, 1], for reasons that will become apparent later on.

Following this stage, a series of similarity matrices for all feature combinations is calculated, in order to determine how related these features are in terms of the information they yield. This step comprises of the computation of three distinct metrics (in the form of three matrices). The metrics used are absolute correlation, similarity (with α = 1) [START_REF] Vachtsevanos | Intelligent Fault Diagnosis and Prognosis for Engineering Systems[END_REF], and 1 -cosine of angle they form [START_REF] Pekalska | The Dissimilarity Representation for Pattern Recognition Foundations and Applications[END_REF]. These metrics were selected so that a significant amount of information about the features can be extracted. Yet, even though this information is more than the information yielded by a single metric, it can be increased if more metrics are added to the list, as long as they all yield values in the interval [0, 1].

After this, a likeliness metric L is calculated by taking the point-to-point product of these matrices and adding I n to it, where n is the number of features in the original feature set. A (feature) potency metric G is also computed, by taking the point-topoint product of vectors C and DR. By taking the ratio of the aforementioned two composite metrics, L and G, yields a distance-like metric D, which constitutes the basis of the feature selection process that ensues. This metric is in essence the evaluation of all the individual features of the original feature set and its presence reduces the original problem into a relatively simple mathematical problem, which is solved in the steps that follow.

Afterwards, the most correlated feature f is selected and its index is stored in vector in (which is the index vector, one of the outputs of the AFS method). This is done because in fault prediction correlation with the wear level plays a vital role for assessing the quality of the condition indicator at hand, so as a starting point one would prefer to have something quite robust. Alternatively, the feature with the highest potency could be selected instead. The inverse of the correlation value of this feature with the wear is stored as the first element of vector X and all "distances" from f to the other features are set to infinite. This is done so that feature f is not selected again. Following that, the "closest" feature to f (let us call it g) is found and its index is stored in in. The "distance" between g and f, in terms of the distance-like metric D, is stored in variable m. The average of X 1 and m is stored in X 2 and all "distances" to g are set to infinite (so that feature g is not selected again either). By repeating the above process for all n features a distance-based feature structure is formed in matrix X and vector in contains the corresponding indexes.

If a correlation threshold th is given, the features from in that yield a C value greater or equal to th are selected while the rest of the features are discarded. Otherwise, the smallest value of X is found (as well as the corresponding index ind) and all features having an in value between 1 and ind are selected. In essence this means that the feature set is partitioned in two clusters, based on D instead of their spatial distances. One of these clusters contains the "good" features, which are taken as an output of the method, while the other contains the "bad" ones, which are discarded. Alternatively, other methods of clustering could be used to achieve this binary partitioning, but this one was selected for its simplicity and effectiveness in practice.

Experiments, Results and Discussion

To test the effectiveness of this method, a set of features extracted from a real-world dataset was used. The features were based on vibration data of axial and radial orientation of the sensors in relation with the bearing examined. The wear levels, four in total including the baseline, corresponded to different corrosion levels of the bearing. Also, the data included two distinct working conditions and were collected over a number of experiment rounds. The feature sets used in this research comprised of 16 features for radial and 16 features for axial data. In both cases they comprised of 240 data points (larger dataset could have been tested by increasing the sampling rate of the features during the extraction process, but this would not change anything in the whole feature selection process, due to the nature of the features in this field). From these feature sets two feature selections were made, one for each set. In the first selection (SF 1 ) which corresponds to the axial features, six features were selected by the AFS method, while for the radial features, the new feature set (SF 2 ) comprised of four features. An additional feature selection was carried out afterwards, this time making use of the union of the original two feature sets. This yielded a subset (SF 3 ) made up of four features (two from each one of the original feature sets).

The experimental setup for the feature selection part is as follows. Using the 240 data points of the dataset, we split them into 10 equal subgroups, using k-fold cross validation, allowing for 216 training points and 24 test points in 10 cross validation groups. These groups are all separately classified across all features within the feature set through a number of classifiers to compare classification performance.

Four classifiers were chosen based on relative speed and accuracy of classification-three of them different flavors of the k-Nearest Neighbor algorithm, thoroughly described in [START_REF] Voulgaris | Discernibility Concept in Classification Problems[END_REF]. For the variants that made use of a k parameter (number of neighbors), the value of 5 was chosen, since it is one commonly used. The classifiers used are the following:

• C4.5 Decision Tree Classifier -(C45) • Variable k-Nearest Neighbor -(VKNN) • Weighted k -Nearest Neighbor -(WKNN) • Discernibility k -Nearest Neighbor -(DKNN)
All six feature sets are classified separately: reduced feature sets for radial, axial, and both features, and total feature sets for the same. For each classification is computed the classification accuracy, measured as percent correct test point classifications; and the CPU time, measured as the number of seconds per classification round. These will measure the ability of the reduced feature set and classifier to properly diagnose the wear level, as well as how long a classifier requires to train itself for diagnosis. These are computed and averaged across 30 iterations of the above procedure, resulting in a total of 300 classification experiments for each combination of feature set and classifier.

A brief analysis of the features selected from the above subgroups of the original feature set is shown in Table 1. Further analysis in the feature subsets yielded by AFS revealed some interesting information that provides insight to the collaborative potential of the selected features. Specifically, the Spherical Index of Discernibility (SID) [START_REF] Voulgaris | Discernibility Concept in Classification Problems[END_REF] was employed, first on the whole feature sets and then on the subset of selected features. As it is expectable, there was a drop in most cases in the SID value when the feature set was reduced, yet this drop was not dramatic, considering the dimensionality reduction ratio (Table 2). Yet, in the case of the combined feature set of 32 features, the reduced feature set yielded a surprising increase in the SID, despite the significant dimensionality reduction ratio exhibited (Table 2). Figure 1 shows the accuracy rate as a percentage of the number of test cases classified correctly per reduced feature set and for each classifier. The feature sets for radial features and for both features, when classified with a KNN-based classifier, show around 90% accuracy in diagnosing the correct wear level.

The time it takes each classifier to train on each feature, as a measure of processing time in seconds, is computed and averaged for all reduced feature sets, and all complete feature sets. The CPU time (Figure 2) shows definite improvement in training time for all four classifiers. Particularly, The C45 and Weighted kNN classifiers, which exhibit an almost 4 times speed up in training time.

Conclusions and Future Work

Based on the previous analysis, it can be concluded that the proposed method yields robust feature subsets, something that reflects in good accuracy rates for fault diagnosis, using a number of classifiers. As one would expect, the accuracy rates in the reduced feature sets are not as high as in the original feature set, since there is some information loss in the feature selection process. However, in the case of the complete feature set of 32 features not only there is no decrease in the accuracy but the opposite is observed. It is also noteworthy that the reduced feature sets are much smaller than the original ones, something that yields significantly better classification speed (based on CPU time). Moreover, the Discernibility of the reduced feature sets appears to not drop significantly, while in one case even increase, after the feature selection takes place. Future work will include alternative measures of (dis)similarity to incorporate in the AFS method. Also, further testing of this method, in different fault feature sets will be conducted to test its generality. Furthermore, it is planned to make use of AFS as a module of a larger system, which will be implemented as an autonomous, fully automated feature generation system taking as inputs preprocessed data and yielding a single fused feature, along with its characteristics, as outputs.

Figure 2 :

 2 Figure 2: Average classification CPU time. Classifiers are, from left to right: Variable kNN, Discernibility kNN, C45, and Weighted kNN.

Figure 1 :

 1 Figure 1: Accuracy of classifiers on reduced and complete feature sets.

Table 1 .

 1 Feature Characteristics. Discernibility refers to the Spherical Index of Discernibility[START_REF] Voulgaris | Discernibility Concept in Classification Problems[END_REF], a measure of class distinguishability.

	Feature	Correlation	Fischer	Discernibility (SID)	Comments
		with Wear	Discriminant Ratio
	# 3, Axial	0.8542	0.9880	0.7292	SF 1 , SF 3
	# 4, Axial	0.6242	0.8286	0.2833	SF 1 , SF 3
	# 9, Axial	0.6859	0.8198	0.3667	SF 1
	# 12, Axial	0.6468	0.7211	0.2375	SF 1
	# 13, Axial	0.8194	0.9733	0.5833	SF 1
	# 16, Axial	0.6759	0.7787	0.4792	SF 1
	Mean, Axial	0.6853	0.7996	0.3352	All features
	# 3, Radial	0.7460	0.9662	0.2583	SF 2
	# 5, Radial	0.6400	0.9992	0.5375	SF 2
	# 8, Radial	0.7082	0.7930	0.2583	SF 2
	# 14, Radial	0.7229	0.9016	0.1833	SF 2 , SF 3
	# 15, Radial	0.6312	0.9993	0.5458	SF 3
	Mean, Radial	0.6871	0.8514	0.3003	All features

Table 2 .

 2 Results of Classification Experiments and Feature Set Evaluation. The Index of Discernibility refers to the Spherical one, introduced and described in[START_REF] Voulgaris | Discernibility Concept in Classification Problems[END_REF]. The numbers in bold denote an improvement.

	Feature Set	Mean Accuracy CPU time	SID	Dimensionality Reduction Ratio
	Axial	94.3%	0.530s	0.6625	-
	Radial	72.0%	0.534s	0.2792	-
	Both	85.6%	0.984s	0.2958	-
	SF 1 (Axial)	85.5%	0.222s	0.5000	62.5%
	SF 2 (Radial)	69.9%	0.152s	0.2583	75.0%
	SF 3 (Both)	86.7%	0.160s	0.6208	87.5%

Acknowledgement

The authors of this paper would like to acknowledge the sponsor of the AVDPIP project, from which the feature data used in this research stems. Also, they would like to thank the rest of the research team involved in AVDPIP, in both the Georgia Institute of Technology and in Impact Technologies.


Yaqing Liu
email: liuyaqing234@yeah.net

Rong Chen

Hong Yang

Algorithms for the Reconciliation of Ontologies in Open Environments

Keywords: Ontology Changes Sequence, Maximum and Sequential Ontology Changes Sequence, Ontology Change

The dynamic changing feature of Semantic Web determines that the ontology which is a part of Semantic Web needs constantly to be modified in order to adapt outer environment. In this paper we make a careful analysis of the ontology changes' complexity under open environment. The main contents discussed are as follow. At first we point out all possible relation types between any two ontology change sequences including directly conflict relation, indirectly conflict relation, dependent relation and compatible relation according to ontology change's definition. And then we propose a new algorithm named Algorithm of Searching Maximum and Sequential Ontology Change Sequence Set(ASMSOCSS) to find all maximum and sequential ontology change sequence subset in the prime ontology change sequence set and prove the independence of the result which may be got after running ASMSOCSS. At last we put forward the algorithm by using these maximum and sequential ontology change sequence sets to create new ontology versions according to the dependence relation between ontology change sequences.

Introduction

Ontology Evolution is the timely adaptation of an ontology to the arisen changes and the consistent propagation of these changes to dependent artifacts. Ontology change disposal, as a part of ontology evolution, focuses on exploring some ontology evolution's methods and technologies to modify ontology on the assumption with not breaking ontology consistency. By far, a lot of research work has been done on ontology change disposal and they may be classified into some based on logical reasoning [6] and others based on belief revision [8] .But all of them mainly focus on ontology change disposal under centralized environment. The research on ontology change disposal under open environment is infrequent. [START_REF] Klein | Change management for distributed ontologies[END_REF] discussed ontology change disposal under open environment for the first time. Its main contribution is to define the mapping relation between any two ontology versions by analyzing these logs of editing ontology. But [START_REF] Klein | Change management for distributed ontologies[END_REF] is not all-inclusive because it can't provide some guide for ontology evolution's trend in semantic level.

Multiple ontology versions will be achieved under open environment. But these ontology versions are not all worthy. Moreover, too many ontology versions will make it more difficult to manage the base of ontology versions. Unfortunately, how to get worthy ontology versions under open environment is seldom concerned. In addition, the problem on ontology change of analysis and disposal is independent of the problem on merging multiple ontology versions. And it is well known that the work of merging ontology versions is very heavy. If the work of merging ontology versions can be integrated into the course of analysis and disposal of ontology changes it will greatly save the work of ontology evolution. In this paper, we propose a new method which may not only create a worthy ontology version but also avoid the work of merging ontologies through analyzing and disposing ontology change sequences.

This paper is organized as follow. The whole scheme of ontology change disposal under open environment is given in section 2. And then we make certain all possible relation types between ontology change sequences in section 3. We propose Algorithm of Searching Maximum and Sequential Ontology Change Sequence Set in section 4 and put forward the algorithm used to create new ontology versions in section 5. Related works are mentioned in section 6 and conclusion and the next work are arranged in the last section.

Description of the Approach

Our approach on ontology change in an open environment is composed of four steps as illustrated in Figure 1.

Step 1: Having accesses to a version O i of an ontology, several users have separate copies O i ' of this ontology in their working spaces.

Step 2: Each user makes changes chs j to his/her copy respectively.

Step 3: Given sequences of users' ontology changes, we algorithmically analyze the relevance between ontology change operations and search for the maximal consistent subset of the whole ontology change operations, which is called the maximal ontology changes set. We put such subsets together and denote them as a collection of ontology change sequences, i.e., {CHS 1 ,CHS 2 ,…, CHS k }, where each CHS i (1ik) represents a maximum sequential ontology changes.

Step 4: Several versions of ontologies may be derived from the original O i by applying one of maximal ontology changes. Obviously, {CHS 1 ,CHS 2 ,…, CHS k } will produce k distinguished ontologies.

The above-mentioned step 3 and step 4 are the crucial parts of our approach, next we will give their details in the remainder of this paper.

O={C,R,H c ,Rel,A o } . (1)
where:  C is the set of ontology concepts.  H C ⊆C×C is a set of taxonomic relationships between concepts.  R is the set of non-taxonomic relationships. The function Rel: R→C×C maps the relation identifiers to the actual relationships.  A o is a set of axioms, usually formalized into some logic language.

For brevity, O is short for ontology throughout this paper. Its instances are denoted by O.I, concept set by O.C, non-taxonomic relationships by O.R. We think of an ontology as a knowledge base, which contains not only the elements of an ontology, but also instances of the concepts C and relationships R.

Stojanovic categorizes all ontology changes into "Add" ontology changes and "Remove" ontology changes respectively. To highlight what type of changes is made to what object, we redefine ontology change as follows: Definition 2: an ontology change ch is defined as: ch={name,type,object,args}.

(

where:

 name is the identifier of this change ch.  type∈{"Add", "Remove"}, is type of ch.  object⊂O. I∪O

……

 args⊂O.I∪O.C∪O.R, is a list of one or more change arguments. There are changes with one, two or three arguments. For example, ch={"AddSubConcept", "Add", {subc 2 }, {supc}} denotes an ontology change that a concept subc 2 is added to an ontology as subconcept of supc. This can be pictured as Figure 2.

Definition 3: an ontology change sequence chs is defined as

chs=<ch 1 ch 2 …ch n >, ch i (1≤i≤n) is an ontology change (4)
if and only if n=1 or ∀1≤i≤n-1, ch i always is executed ahead of ch i+1 .

Argument Pool and Remove Pool of an Ontology Change Sequence

For an ontology change sequence chs=<ch 1 ch 2 …ch n >, the argument pool of chs is used to enumerate all ch i .args when ch i .type is "Add" and the remove pool of chs is used to enumerate all ch j .object when ch j .type is "Remove". Further, the argument pool chs.APool and the remove pool chs.RPool of an ontology change sequence chs=<ch 1 ch 2 …ch n > can be obtained when we apply the ACAPRP algorithm to chs. Given a simple example illustrated in Fig. 3, we suppose:  chs=<ch 1 ch 2 >  ch 1 ={"RemoveConcept", "Remove",{subc 2 },{}}  ch 2 ={"AddSubConcept", "Add",{subc 3 },{supc}} When ACAPRP algorithm is applied to chs the output is chs.RPool={subc 2 } and chs.APool={supc}. supc

Relation Types between two Ontology Change Sequences

Algorithm of Searching Maximal Ontology Changes Set

According to the relation type between two ontology change sequences, four lemmas may be deduced.

Lemma 1: If an ontology change sequence chs 1 directly conflicts with another ontology change sequence chs 2, not all of chs 1 and chs 2 are executed no matter what the execution order may be.

Lemma 2: If an ontology change sequence chs 1 depends on another ontology change sequence chs 2 , chs 1 and chs 2 can be all executed if and only if chs 2 is executed ahead of chs 1 .

Lemma 3: If an ontology change sequence chs 1 indirectly conflicts with another ontology change sequence chs n , not all of chs 1 and chs n are executed no matter what the execution order may be.

Lemma 4: If an ontology change sequence chs 1 is compatible with another ontology change sequence chs 2 , chs 1 and chs 2 may always be executed no matter what the execution order may be.

According lemma 1,2,3 and 4, if any two of a group of ontology change sequences are not directlyConflict or indirectlyConflict all these ontology change sequences may be executed. In order to find all maximum subset of all ontology change sequences Algorithm 1:ACAPRP(chs) Input: an ontology change sequence <ch [START_REF] Klein | Change management for distributed ontologies[END_REF] 6 Related Work

Ontology versioning [5] typically involves the storage of several ontology versions and identification issues, the relationship between different versions as well as compatibility information. [START_REF] Noy | Ontology evolution: Not the same as schema evolution[END_REF] uses the term versioning to describe their approach of ontology change. They define ontology versioning as the ability to manage ontology changes and their effects by creating and maintaining different variants of the ontology. Adequate methods and tools must be used to distinguish and identify the versions. [START_REF] Plessers | Ontology change detection using a version log[END_REF] presents a new ontology evolution approach. The approach keeps track of the different virtual versions of ontology concepts throughout their lifetime by combining the manual request for changes by the ontology engineer with an automatic change detection mechanism. [START_REF] Huang | Reasoning with multi-version ontologies: A temporal logic approach[END_REF] proposes a logic framework used to reason with multversion ontologies. In the framework such problems can be solved as querying log of semantic change, selecting a appropriate ontology version, etc.

Conclusion and Future Work

We propose a formal method used to analyze and dispose a group of ontology change sequences under open environment. But our discussion is specific to the same ontology subject to a group of ontology change sequences. In future, we will use graph theory to rephrase such a problem.

Fig. 1 .

 1 Fig. 1. Description of our approach

Fig. 3 .

 3 Fig.3. An illustration of an ontology change sequence.

Fig. 2 .Fig. 2 .

 22 Fig.2. An illustration of an ontology change.

  Definition 4: An ontology change sequence chs 1 depends on another ontology change sequence chs 2 if and only if chs 1 .RPool ∩ chs 2 .APool≠∅ ∧chs 2 .RPool ∩ chs 1 .APool=∅ . dependence(chs 1 ,chs 2 ) means that chs 1 depends on chs 2 and ¬dependence(chs 1 ,chs 2 ) means that chs 1 doesn't depend on chs 2 . APool≠∅ ∧chs 2 .RPool∩chs 1 .APool≠∅ . directlyConflict(chs 1 ,chs 2 ) means that chs 1 and chs 2 directly conflict with each other and ¬directlyConflict(chs 1 ,chs 2 ) means that chs 1 and chs 2 don't directly conflict with each other.

	Definition 5: An ontology change sequence chs 1 directly conflicts with another
	ontology change sequence	chs 2 if	and	only	if	chs 1 .RPool ∩
	chs 2 .

  Definition 6: For a few of ontology change sequences chs 1 , chs 2 , …,chs n , chs 1 indirectly conflicts with chs n iff dependence(chs 1 ,chs 2 ), dependence(chs 2 ,chs 3 ),…, dependence(chs n ,chs 1 ) all are true, where indirectlyConflict(chs 1 ,chs n ) means that chs 1 and chs n indirectly conflict with each other and ¬indirectlyConflict(chs 1 ,chs n ) means that chs 1 and chs n don't indirectly conflict with each other. Definition 7: An ontology change sequence chs 1 is compatible with another ontology change sequence chs 2 iff chs 1 .RPool ∩ chs 2 .APool=∅ ∧chs 2 .RPool ∩ chs 1 .APool=∅ , where compatible(chs 1 ,chs 2 ) means that chs 1 and chs 2 are compatible each other.

	supc
	subc 1	subc 1	subc 2

Algorithm of Generating New Ontology Versions According

  Return chs.RPool and chs.APool that may be executed from a given group of ontology change sequences, we propose the Algorithm of Searching Conflict Set(ASCS) to be used to find all ontology change sequence pairs which indirectly conflict or directly conflict with each other and the Algorithm of Searching Maximum and Sequential Ontology Change Sequence Set (ASMSOCSS). Definition 8: Given a group of ontology change sequences CHS={chs 1 , chs 2 ,……, chs n } , MSOCSS CHS is defined as Maximum and Sequential Ontology Change Sequence Set if and only if ¬∃T⊆CHS makes all T⊃MSOCSSM CHS and ∀t 1 ,t 2 ∈T, ¬directlyConflict(t 1 ,t 2 )∧¬indirectlyConflict(t 1 ,t 2 ) to be true. In ASMSOCSS, step 2 means to traverse all elements of CONF in unknown order. It is puzzling whether the order of traversing elements can change the final MSOCSSSet or not. The problem can be explained by lemma 5. Lemma 5: The final MSOCSSSet is identical no matter what the order of traversing elements may be. Proof ∀(e1,e2),(e3,e4)∈CONF, e1∈CHS∧e 2 ∈CHS∧e 3 ∈CHS∧e 4 ∈CHS is given. Suppose that e 1 ≠e 3 ∧e 1 ≠e 4 ∧e 2 ≠e 3 ∧e 2 ≠e 4 ∧e 1 ≠e 2 ∧e 3 ≠e 4 is true. If (e1,e2) is traversed ahead of (e3,e4) , MSOCSSSet 0 ={CHS/{e 1 },CHS/{e 2 }} is got. After (e3,e4) is traversed, MSOCSSSet 1 ={CHS/{e 1 ,e 3 } , CHS/{e 1 ,e 4 } , CHS/{e 2 ,e 3 }, CHS/{e 2 ,e 4 }} is got. In turn, if (e3,e4) is traversed ahead of (e1,e2) , MSOCSSSet 0 ={CHS/{e 3 },CHS/{e 4 }} MSOCSSSet 2 ={CHS/{e 3 ,e 1 } , CHS/{e 3 ,e 2 } , CHS/{e 4 ,e 1 }, CHS/{e 4 ,e 2 }} is got. Obviously MSOCSSSet 1 =MSOCSSSet 2 .MSOCSSSet 1 =MSOCSSSet 2 is easy proved when e 1 =e 3 ∧e 1 ≠e 4 ∧e 2 ≠e 3 ∧e 2 ≠e 4 ∧e 1 ≠e 2 ∧e 3 ≠e 4 is true. ∀(e1,e2),(e3,e4)∈CONF, the same conclusion may be drew easily whichever of e1CHS∧e 2 ∈CHS∧e 3 ∈CHS∧e 4 ∈CHS or e1 CHS∧e 2 CHS∧e 3 ∈CHS∧e 4 ∈CHS or e1 CHS∧e 2 ∈CHS∧e 3  CHS∧e 4 ∈CHS or e1 CHS∧e 2  CHS∧ e 3 CHS∧e 4 CHS is given. to ASMSOCSS, ∀E∈MSOCSSSet, ∀(e 1 ,e 2 )∈E, e 1 must not directly conflict or indirectly conflict with e 2 . So ∀E∈MSOCSSSet, all elements in E are executed once. When a MSOCSS CHS is applied to an ontology O, a new ontology version can be got. The algorithm of generating a new ontology version is AGNOV. Algorithm 3:ASMSOCSS(CHS,CONF) Input:a group of ontology change sequences {chs 1 , chs 2 ,……, chs n } and ASCS({chs 1 , chs 2 ,……, chs n }) Output:the set of all possible maximum and serial ontology change sequence

		Algorithm 2:ASCS(CHS)
	Input:a group of ontology change sequences {chs 1 , chs 2 ,……, chs n } ch 2…… ch n > Output:a conflict set CONF Output:chs.RPool,chs.APool 1. chs.RPool←Ø; chs.APool←Ø; 1. CONF←Ø; i1←1; i2←1; i←1; 2. WHILE(i1<=n) 2. WHILE(i<=n) 3. 3. WHILE(i2>=i1 and i2<=n) chs.APool←chs.APool∪ch i .args; 4. IF ch i .type="Remove" 5. 4. IF(directConflict(chs i1 ,chs i2 ) or indirectConflict(chs i1 ,chs i2 )) and i1  i2 chs.RPool←chs.RPool∪ch i .object; 6. 5. CONF←CONF∪{{chs i1 ,chs i2 }}; IF ch i .type="Add" and ch i .object⊆chs.RPool 7. 6. i2++; chs.RPool←chs.RPool-ch i .object 8. 7. i1++; i2←i1; i++; got. After (e1,e2) exchangeable. Further, Lemma 5 may be deduced easily according to related is mathematical characteristics. 11. RETURN MSOCSSSet □ 2. FOR EACH (chs 1 ,chs 2 )∈CONF 3. FOR EACH e∈MSOCSSSet 4. IF chs 1 ∈e and chs 2 ∈e 5. MSOCSSSet←MSOCSSSet-{e}; 6. e 1 ←e-{chs 1 }; e 2 ←e-{chs 2 }; 7. IF  ∃e'∈CAND , e 1  e' 8. MSOCSSSet←CAND∪{e 1 }; 9. 10. MSOCSSSet←CAND∪{ e 2 }; IF  ∃e'∈CAND , e 2  e' traversed ,So we may know that the order of traversing any two elements of CONF is set MSOCSSSet 1. MSOCSSSet←{CHS}; i1←1; i2←1; 9. is 8. RETURN CONF
	5	Algorithm 4:AGNOV(O) Input:an ontology O
		Output:the set of all new ontology version OVs
	1. OVs←Ø;
	2. FOR EACH E∈MSOCSSSet
	3.	O'←O;
	4.	WHILE(E≠Ø)
	5.	IF ∃ chs i ∈E,∀ chs j ∈E/{chs i },  dependence(chs i , chs j )
	6. 7.	O'←chs i (O); E←E/{chs i }; OVs←OVs { ∪ O'};

The corresponding Author. This work was supported by National Natural Science Foundation of China (60775028), Dalian Science &Technology Program (2007A14GX042),Young Key Teachers Foundation Projects of Dalian Maritime University (2009QN034)


Samira Guennif Valérie

Revest Cepn

SOCIAL STRUCTURE AND REPUTATION: THE NASDAQ CASE STUDY

Keywords: NASDAQ, non-competitive behaviours, embeddedness, social structure, game theory, reputation, trust. Classification JEL: A12, A14, B41, L14, G14, G15

. We propose the use of game theory tools to achieve this goal. A rereading of Kreps' model of reputation sheds light on its structural dimension and illustrates the way social structure governs individual behaviours.

Introduction

In 1994, the Securities and Exchange Commission (SEC) and the American Department of Justice conducted investigations into market makers' operations on the NASDAQ. These investigations reported non-competitive transactions [START_REF] Revest | Microstructure, institutions et marchés financiers organisés[END_REF]. Market makers followed numerous illicit practices such as price collusion or the spreading of private information. These practices belonged to a collective pattern: most market makers observed social norms in order to increase significantly their income at the expense of the customers. The evidence illustrates the influence of the social structure on individuals' behaviours and on the progress of transactions.

Although standard economics does study social interactions, it favours an atomistic point of view; individuals are astructural [START_REF] Degenne | Les réseaux sociaux[END_REF]. The theory disregards the social context, since markets are assumed to be competitive and the price mechanism allows mediation between anonymous individuals [START_REF] Hirschman | Vers une économie politique élargie[END_REF]. On the contrary, Granovetter puts forward a conception of exchange which highlights the embeddedness of economic actions within social structures: "the argument that the behaviour and institutions to be analyzed are so constrained by ongoing social relations that to construe them as independent is a grievous misunderstanding" (1985, p. 482). Even if the argument takes into account the role of social structures, it remains "a programmatic statement" [START_REF] Uzzi | The sources and consequences of embeddedness for the economic performance of organizations: the network effect[END_REF] 1 . This paper aims to explain how non-competitive behaviours emerged on the NASDAQ, through a concrete view of embeddedness. Game theory tools and particularly Kreps' model of reputation are mobilised (Kreps, 1990a(Kreps, , 1990b)). At first glance, Kreps' model belongs to an under-socialised view of action: "narrow utilitarian pursuit of self-interest" induces the behaviours of economic actors (Granovetter, 1985, p. 485). However, a rereading of this model discloses its important implicit content, shedding light on its structuralist dimension and consequently helping to explain the way social structures govern actors' behaviours [START_REF] Guennif | Incertitude, confiance et institution en échange marchand. Recherche sur les fondements de la confiance dans le secteur de la mécanique de précision[END_REF]. In other words, the purpose of this paper is to initiate a link between Granovetter's works on embeddedness and game theory, by means of an interdisciplinary method.

Firstly, the main conclusions of the investigations conducted by the SEC and the Department of Justice about the deficiencies of the NASDAQ in 1994-1996 are scrutinised. Evidence shows that some non-competitive behaviour had been stimulated by the social structure of the NASDAQ. Secondly, after analysing Kreps' model, we describe the role of trust, rational motives and social norms in the functioning of social structures. These elements generate a particular enforcement that sustains non-competitive behaviours and underlies the progress of transactions on this market.

Impediments to price competition on the NASDAQ stock market

The SEC's investigation revealed that the NASDAQ has not always operated in an open and freely competitive manner. "NASDAQ market makers have engaged in a variety of abusive practices to suppress competition and mislead customers" (US Securities and Exchange Commission, 1996, p. 3). In this section, we describe the main anti-competitive practices highlighted by the investigations. Then, we show that the market makers' behaviours have been influenced by the structure of the NASDAQ Stock Market. This approach corroborates the embeddedness argument of Granovetter: market makers' behaviours are constrained by social relations.

1. A brief description of the NASDAQ Stock Market in 1994

Initially intended to enhance the efficiency of the Over-The-Counter (OTC) market for stocks, the NASDAQ, founded in 1971, has experienced remarkable growth and represents a serious competitive alternative to the dominant equity exchange in the US, the New York Stock Exchange (NYSE).

The NASDAQ market is a telecommunications network linking thousands of geographically dispersed market participants. This is exclusively a dealer's market, in which a number of brokers-dealers make markets in the same security2 . Making a market consists in standing ready to buy and sell securities at displayed prices. The market makers in NASDAQ quote two prices: a "bid" price, at which they are willing to buy the security, and an "ask" price, at which they are willing to sell the security. Each issuer has at least two market makers for its stock, but the average stock has eleven market makers.

Market makers seek profit by buying at lower prices and selling at higher prices (a market maker's bid price will always be lower than their ask price). The difference between the ask price and the bid price is called the "dealer spread". The spread represents part of the market maker's potential compensation. Market makers play an important role in financial markets. Demand for market making generally arises because buyers and sellers of securities do not arrive at the market at the same time or with the same quantities to trade. The market maker is thus said to provide immediacy to the market [START_REF] O'hara | Market Microstructure Theory[END_REF][START_REF] Schwartz | Reshaping the equity markets: a guide for the 1990s[END_REF].

The quotes are displayed on the NASDAQ market's electronic quotation system. The highest bid and lowest ask prices are also separately displayed together as the "inside quotes", and the difference between the two is called the "inside spread". Display of the inside quotes allows a viewer to observe immediately the best prices quoted on the NASDAQ market for both buying and selling a given security.

Market makers in NASDAQ have to respect certain rules. They must display two-sided quotes in all stocks in which they choose to make a market, from 9.30 a.m. to 4.00 p.m., from Monday to Friday. They have to propose firm quotes. When executing a customer order, market makers are required to seek the most favourable terms for the customer under the circumstances. Market makers must also report their trades to the NASDAQ market on time. Created in 1939, the National Association of Securities Dealers (NASD) operates and regulates the NASDAQ3 .

The price convention and other market makers' non-competitive behaviours

In 1994, an article by Christie and Schultz revealed larger dealers' spreads on NASDAQ than on the NYSE. As a result, the Antitrust Division of the US Department of Justice began an antitrust investigation of NASDAQ market makers, while the SEC began an investigation of the NASD (US Department of Justice, 1996, US Securities andExchange Commission, 1996). These investigations involved extensive analysis of market data, interviews with market participants, and review of taped conversations between market makers4 . Both investigative teams found several abusive practices.

Firstly, NASDAQ market makers widely followed a price convention. This convention was used to determine the increments by which they would adjust the displayed quotes. Market makers testified that under the convention, stocks in which dealers were quoting spreads of $3/4 or more had to be quoted in even-eighths (i.e. $1/4, $1/2, $3/4), thereby giving rise to a minimum inside spread of $1/4. Stocks with dealer spreads lower than $3/4 could be quoted in both even and odd-eighths, thereby allowing a minimum inside spread of $1/8. Therefore, the price convention limited the flexibility and competitiveness of price quotation in the NASDAQ market. In the case of quoted spreads equal to or greater than $3/4, the avoidance of oddeighth quote increments meant that the inside spread could not be narrowed to $1/8. On one side, as the spread represents part of the market markers' compensation for providing immediacy, the convention resulted in a larger compensation for them. On the other side, market makers' adherence to this price convention often increased the transaction costs paid by customers. In effect, the price convention resulted in wider inside spreads, which caused trades to be executed at prices that were less favourable for investors5 .

Secondly, many NASDAQ market makers also adhered to a size convention, under which they did not display a new inside quote unless they were willing to trade in an amount substantially greater than the minimum volume required by NASD rules. In 1994, these rules required market makers to be willing to trade at least 1,000 shares at their quoted prices for the more actively traded stocks and lesser amounts for other NASDAQ stocks. The size convention had an anti-competitive effect. It inhibited price transparency by limiting quote changes and resulted in large spreads.

Thirdly, the investigations established that a number of NASDAQ marker makers coordinated quotations, trades and trade reports with other NASDAQ market makers. On numerous occasions, market makers asked colleagues to shift their displayed quotations in a particular direction in order to help the requesting market maker to trade at the most favourable prices. Cooperating market makers acceded to these requests as they expected the requesting market maker to reciprocate in the future. Such cooperative activity improperly influenced prices, often at the expense of investors. Moreover, evidence demonstrated that market makers regularly shared information relating to the size of customer orders and sometimes to the identity of the customer. Market makers also shared information concerning their own inventory positions, their intended trading strategies and future quote movements. These practices, viewed as "courtesy", could conflict with the basic obligations of a broker-dealer toward his customers. For example, revealing the size of a customer order could be detrimental to the ability of the customer to obtain the best execution.

Fourthly, the investigation revealed numerous violations of the firm quote rule by NASDAQ market makers. Market makers have a fundamental obligation to honour their quotations. Failure to honour quotations deprived investors of the liquidity market makers could provide. For instance, market makers at times backed away from their trading obligations to avoid unwanted orders.

Finally, we can mention the practice of "late trade reporting". Numerous market makers repeatedly failed to report NASDAQ transactions on an accurate and timely basis. The Commission staff calculated that at least 3.6% of all NASDAQ trades in the period between February and December 1994 were reported late. During the same period, late trades accounted for only 0.9% of reported trades on the New York Stock Exchange. As reports of large trades are more likely to be market sensitive, market makers seeking to fill an order or cover a position may have a greater incentive to delay the reporting of large trades.

In summary, according to the investigation reports, market makers widely followed conventions, during the period 1994-1996, that were opposed to the general rules of the SEC governing the functioning of American financial markets. One important issue relates to the way the behaviours described above expanded. In other words, how did non-competitive practices emerge and spread on the NASDAQ?

3. Social relations on the NASDAQ

When questioned about these non-competitive practices, market markers insisted paradoxically on their ethical nature, which, they argued, justified the use of sanctions. The NASDAQ pricing convention was generally considered as a pricing "ethic", "tradition" or "professional norm". Violating the convention (in the parlance of market makers "breaking the spread") was regarded as "unprofessional" or "unethical" trading behaviour (US Department of Justice, 1996, p. 21). Market makers who deviated from the convention were derisively said to create a "Chinese market". Numerous witnesses testified to this fact. One market maker admitted that he telephoned another market maker to make him change his quotation: "To get him to get his increment and his spread to conform to what I thought was the right thing to do" (US Securities and Exchange Commission, 1996, p. 18).

"Insert Evidence 1"

Remarkably, market makers were not alone in perceiving the price convention as a professional norm. According to the Letter of the Securities Traders Association of New-York (3 rd quarter, 1989), "It is clearly unethical to make a Chinese market". During a meeting in June 1990, the NASD's Trading Committee also concluded that the price convention was an internal ethical issue.

Market makers enforced adherence to the price convention in different ways. Traders testified that they were taught (by the senior traders) to follow the convention. Therefore, they followed it and they expected other traders to follow it as well.

In addition, market makers who violated the price convention were subjected to harassing telephone calls. Traders testified that the telephone calls were effective in deterring market makers from entering quotes that were inconsistent with the pricing convention. In general, the mere threat of such harassment was sufficient to discourage market makers from violating the convention. One trader explained why, when he was a junior trader, these telephone calls dissuaded him from narrowing spreads, stating: "because, many years ago, as a junior trader, I wanted to be accepted" (US SEC, 1996, p. 18).

"Insert Evidence 2"

Firms that repeatedly entered quotations in violation of the quoting convention were punished. The most effective mechanism was the refusal to deal. A refusal to deal has negative consequences for market makers. For example, when a market maker does not want to fill a retail or institutional order from his own account, he must be able to find other market makers willing to fill this order. Otherwise, his clients will soon look elsewhere for trading services. Consequently, the threat that other firms will not trade with them was often sufficient to discourage market makers from violating the convention.

When a market maker violated the convention, he was subject to harassment and punishment. He no longer had access to the informal resources of the traders' network and his remuneration therefore fell. If, on the other hand, he followed the convention, then he gained access to private information, and could take advantage of the opportunities offered by the network.

In conclusion, the investigations conducted by the SEC and the US Department of Justice revealed the influence of the NASDAQ's structure on the behaviours of market makers. In order to understand this influence more clearly, we shall illustrate the embeddedness argument by means of Kreps' reputation model. Even if [START_REF] Granovetter | Economic action and social structure: the problem of embeddedness[END_REF] asserts that game theory propositions belong to an under-socialised view of social relations, we now propose a new reading of Kreps' reputation model. This rereading makes it possible to overcome the undersocialised bias and, above all, to grasp the way social structures may influence individuals' behaviour.

Kreps' model of reputation: from an atomistic to a structuralist view of interaction

For transactions in which free-riding behaviour is a feature, game theory tries to define the conditions required for the emergence of cooperative behaviour and the achievement of an optimal equilibrium. In this perspective, Kreps asserts that the prisoner's dilemma is solved in infinitely repeated games among n players when a self-enforcing mechanism built upon strict economic incentives produces trust and induces cooperative behaviour. This mechanism is reputation. It satisfies a huge theoretical objective: the obtaining of a private arrangement capable of sustaining spot-market transactions. Yet, according to us, reputation operates within social structures where the embeddedness of players activates social mechanisms for the performance of transactions. Hence, reputation and others mechanisms such as trust, solidarity and ostracism are part of a social arrangement that underlies the performance of any transaction, such as those between market makers.

1. The atomistic dimension and private arrangement

Kreps analyses a very particular game. On first sight, it is an one-round game: an actor A i must decide whether or not to trust an actor B. A i knows that if he elects to interact with B, the latter can choose to act opportunistically, as a free rider. B may impose severe losses on A i and obtain maximum gains. This is the "selfish temptation" [START_REF] Axelrod | The Evolution of Cooperation[END_REF]. Trust is the risk A i takes on B's behaviour [START_REF] Luhmann | Trust and Power[END_REF][START_REF] Dasgupta | Trust as a commodity[END_REF][START_REF] Coleman | The foundations of social theory[END_REF][START_REF] Lorenz | Flexible production systems and the social construction of trust[END_REF][START_REF] Guennif | Incertitude, confiance et institution en échange marchand. Recherche sur les fondements de la confiance dans le secteur de la mécanique de précision[END_REF].

In fact, the game is repeated: B must successively decide whether to honour or to abuse the trust of A 1 , A 2 , A 3 , ... A n . The game thus begins with a single transaction between actors A 1 and B and continues with another transaction between A 2 and B, and so on. So, "instead of having one individual who offers trust and a second who honours or abuses that trust, we have a sequence of individuals A who must choose whether or not to trust a single trading partner B" (Kreps, 1990a, p. 106). Kreps posits that the game is infinitely repeated: there is a 90 percent chance that another transaction will follow the present one.

Kreps then specifies the conditions required for the transactions between actors A i and B to take place. On the one hand, any A i will only trust B if B has not abused the trust of his previous partners. Thus, the past behaviour or the reputation of B determines the choice of each A i for the present round. On the other hand, B knows that if he wants to exchange with another A i for the next round, he must preserve his reputation. In other words, he must honour his partner's trust in the present round. To sum up, B maintains his reputation unsullied by honouring A i 's trust, and thus obtains the possibility of repeated transactions with them. In this way, B gains maximum profits through repeated rounds. He receives $10 in each round, according to the Kreps' Trust game (1990a, p. 100). On the contrary, if B abuses the trust of the current A i , his reputation is irremediably sullied. He gets the maximum pay-off resulting from defective behaviour ($15), but he can no longer transact with A i . By choosing opportunistic behaviour, B renounces the $10 for each honest future transaction he would have had with A i . B will therefore choose to protect his reputation, an asset that will give him high levels of income in the future. Each A i knows that B is rational and will keep his reputation unsullied by honouring the trust of his partners. For this reason, each A i will decide to trust B and will choose to transact with him. Thus, reputation is a "process-based" mechanism linked to the repetition of transactions (Zucker, 1986 p. 60). Finally, the mechanism is built upon the expectation that the business partner will behave more or less as he did in the past6 .

Ultimately, Kreps' propositions overcome the prisoner's dilemma and satisfy significant theoretical objectives. For example, as an informal self-enforcing mechanism, reputation supports the progress of spot-market transactions. Reputation produces the trust necessary for the occurrence of transactions that contain a risk of opportunistic behaviour, of strategic or behavioural uncertainty [START_REF] Williamson | The economic institutions of capitalism[END_REF]. Thanks to reputation, a "self-enforcing arrangement" can be found; there is no need for any third party involvement or arbitration [START_REF] Lester | A theory of self-enforcing agreements[END_REF][START_REF] Klein | Transaction cost determinants of "unfair" contractual arrangements[END_REF]. To put it differently, the progress of transactions relies on a private arrangement, which is all the more efficient in the neo-institutional sense of the term. The informal self-enforcing mechanism explains how transactions take place without any complete contingent contract 7 . Trust thus based on reputation saves on transaction costs [START_REF] Arrow | The limits of organization[END_REF][START_REF] Leibenstein | Inside the Firm: The Inefficiencies of Hierarchy[END_REF]Kreps, 1990a;[START_REF] Sako | Price, quality and trust: Inter-firm relations in Britain and Japan[END_REF][START_REF] Guennif | Incertitude, confiance et institution en échange marchand. Recherche sur les fondements de la confiance dans le secteur de la mécanique de précision[END_REF].

Despite these important theoretical points, the trust game has certain limits (Kreps, 1990a, p. 103). For instance, Kreps recognises that his construction "depends crucially on each A seeing precisely how B has behaved previously" (Kreps, 1990b, p. 71) and leads to many equilibriums. B may say to A i "I intend to honour your trust two out of three times and to abuse it once every three times" (Kreps, 1990a, p. 102). The 90 percent chance that the game will go on after the present round is also arguable. Nevertheless, our objection lies on a different level: the model does not belong to an atomistic view of interaction. A rereading of this model discloses its structuralist dimension.

2. The structuralist dimension of the model

Strictly, following Kreps' propositions, reputation produces a particular link between each A i and B, i.e. trust. Trust motivates cooperative behaviour and induces transactions. In the diagram below, this trust links figures in bold type to indicate that it supports an exchange that involves the two players. According to us, the argument is much more complex than Kreps' assertions suggest. Any transaction between A i and B occurs thanks to several trust links. In order to make this point explicit, let us consider a transaction: A 2 must decide to trade with B. What are the conditions of trust among players and what are the conditions for the occurrence of a transaction? Firstly, for reputation to be the self-enforcing mechanism, A 2 must be able to observe B's behaviour during the previous transaction. Kreps assumes such a capacity. On the contrary, Kandori argues that "the agent only observes the results of the trades he is engaged in" (1992, p. 65). Because of imperfect observability, A 2 identifies at best A 1 and requests his "private information", asks for his "personal experience" (p. 64). Then, the decision whether to trust B depends on A 2 's access to the information A 1 holds and above all on the credit A 2 gives to this information. As shown in the diagram, another trust link appears and underlies Kreps' reputation construction: if A 2 trusts A 1 to communicate his private information without any distortion, and if A 1 claims that B acts honestly, then A 2 elects to trust B and exchange with him 8 . When one of these conditions is not satisfied, A 2 refuses to trust B and renounces trade with him 9 .

The prime trust link that binds A 2 and A 1 is a necessary condition for the development of trust between A 2 and B. A 1 is "a trustworthy informant" [START_REF] Granovetter | Economic action and social structure: the problem of embeddedness[END_REF], an "intermediary in trust" [START_REF] Coleman | The foundations of social theory[END_REF][START_REF] Nooteboom | The triangle: roles of the go-between[END_REF][START_REF] Uzzi | The sources and consequences of embeddedness for the economic performance of organizations: the network effect[END_REF], a "third party" [START_REF] Burt | Entrepreneurs, distrust and third parties: a strategic look at the dark side of dense networks[END_REF]. Trust connecting A 2 and B displays a medial nature since it presupposes a former trust link between A 1 and A 2 . Hence, one may consider the existence of a "trust chain" [START_REF] Coleman | The foundations of social theory[END_REF]).

7 This is a critical point since actors are unable to draft contingent contracts; they face difficulties in measuring individual performance, in observing compliance [START_REF] Alchian | Production, information costs and economic organization[END_REF][START_REF] Hart | Firms, contracts, and financial structure[END_REF] and in predicting. Finally, bounded rationality impedes the drafting of complete contracts [START_REF] Simon | Rationality as process and as product of thought[END_REF]. 8 In other words, to trust B, A 2 must have information about B's reputation (his past behaviour), and A 1 's reputation (his capacity to give good information about his partners' behaviour). 9 If the transaction ends up with problems between A 1 and B, A 1 can declare that he has been cheated by an opportunist. In the same circumstances, B can declare he has fulfilled his obligations, that A 1 was unlucky. Therefore, the question of the credit A 2 gives to A 1 arises. A 1 may declare that he has been cheated to hide his undue requirements. Then B may refuse to commit his reputation and may renounce trade with such individuals [START_REF] Lorenz | Neither friends nor strangers: informal networks of subcontracting in French industry[END_REF].

Secondly, before trusting B, A 2 must be sure that any opportunistic behaviour on the part of B will be punished by A 3 , i.e. the player who will next decide whether to exchange with B. Therefore, A 2 's trust relies on the belief that A 3 will ostracise B in the case of opportunism. Introducing a doubt about B's next partner, it follows that the trust A 2 invests in B depends on the belief any A i will boycott transaction with an opportunist B. Thus, as shown in the diagram, A 2 decides to trust B and exchange with him under the condition that A 2 believes that A i will ostracise B if he defects.

Consequently, to ostracise B for opportunistic behaviour, all A i must ultimately rely on the private information A 2 delivers. A i necessarily trusts A 2 . Trust between A 2 and A i is therefore mutual, as the two-way arrows in the following diagram illustrate.

To sum up, the accomplishment of a transaction between any A i and B is not due to a single trust link between the two players, as Kreps stated. According to our argument, it relies on several trust ties: A 2 trades with B if he trusts him, if he trusts his peers and if they trust him in return. When one of these trust links is not fulfilled, A 2 renounces the exchange with B. These trust connections make up the following "chain of trust": "Insert Figure 1" At this point, a significant gap arises between the reputation argument set out by Kreps and the outcome of a careful examination of his model. Following the latter, all the conditions required for the progress of any transaction ultimately suggest that players operate within social structures. Thus, the assertion that transactions take place within a private arrangement characterised by a self-enforcing mechanism is questionable. Our argument is that transactions take place thanks to a "social arrangement" [START_REF] Uzzi | The sources and consequences of embeddedness for the economic performance of organizations: the network effect[END_REF] featuring a specific enforcement that we shall define below. In other words, against all expectations, a new reading of this model can be used to illustrate Granovetter's embeddedness hypothesis10 .

Embeddedness and non-private enforcement of transactions

According to us, reputation operates neither solely nor within a private arrangement. The reputation mechanism is one among several elements comprising the "structural enforcement" [START_REF] Guennif | From bilateral enforcement to structural enforcement in economic exchange[END_REF], which ensures the accomplishment of transactions within social structures.

In sociological literature, a social structure represents an organisation of economic life in which formal and informal social relations among actors matter. Here, social relations among players contribute to the progress of any transaction on the basis of trust given or received within the network, i.e. "a saturated structure in which every actor is directly linked to every other individual" (Knoke and Kuklinski, 1990, p. 175) and where "a specific type of relation links a defined set of persons" (Mitchell, 1969, p. 45). These social structures influence economic decisions: all transactions are shaped by and depend on social relations among actors. This influence refers to Granovetter's embeddedness. Accordingly, transactions occur within a web of social relations whereby actors are bound and influenced in one way or another by systems of more or less stable and lasting social relations, within which tangible and intangible resources such as materials, money, information, knowledge, norms or rules diffuse and circulate [START_REF] Guennif | From bilateral enforcement to structural enforcement in economic exchange[END_REF].

Concretely, the influence of social structures on players' behaviour is possible through the operation of a non-private enforcement of the accomplishment of transactions. Enforcement refers to the formal and informal mechanisms defined and used by actors to inhibit opportunism and to incite cooperative behaviour so that transactions can take place [START_REF] Guennif | From bilateral enforcement to structural enforcement in economic exchange[END_REF] 11 . For us, the acknowledgement of embeddedness clarifies the path from private enforcement to structural enforcement, in which reputation plays a role and players' motivations for action are much more complex.

As figure 2 summarises, trade conditions result on the left-hand side from an undersocialised vision of action. In order to fulfil theoretical propositions, social structure is neglected and a private arrangement is proposed through the reputation mechanism. The enforcement of transaction relies strictly on a bilateral foundation: two players trust each other and exchange thanks to formal and informal mechanisms built upon economic incentives. These mechanisms are defined and used by players to prevent opportunism from their partners and to facilitate the accomplishment of transactions. In this perspective, reputation produces economic incentives not to cheat and induces individual actions sufficient for the efficient enforcement of spot-market transactions: A 2 trusts B and agrees to exchange with him because he believes B will not cheat because he values his reputation as the condition for present and future gains.

On the right-hand side, social structure is taken into account. Consequently, trust is all the more important as a lubricant for its functioning. Players' behaviour is influenced by the social context, which makes it easier to resort to a structural enforcement that goes beyond the private arrangement, the bilateral enforcement described by Kreps. This enforcement expresses the idea that relationships between actors shape behaviour in ways neglected by standard economic theory. Resorting to social mechanisms hinders opportunism and induces cooperative behaviour during market transactions. Hence, the rational motive (preserving reputation) and social norms (solidarity, ostracism or reciprocity) are both involved in the accomplishment of transactions.

Indeed, Granovetter's proposition concerning the joint involvement of selfish and unselfish motives in the accomplishment of transactions is confirmed. B protects his reputation as an asset that represents important future income. In addition, A 2 chooses to exchange with B because he believes that peers will sanction any defection by refusing to transact with B in the future 12 . Ostracism is therefore an internal voice attitude that derives from trustworthiness, loyalty towards peers [START_REF] Hirschman | Vers une économie politique élargie[END_REF]. It is a social norm deriving from potential sanction within a community when improper behaviour is observed [START_REF] Elster | Social norms and economic theory[END_REF]. Therefore, utility maximisation and social norms play both a major role in the functioning of social structures. To put it differently, the rationality principle is insufficient and other motives, such as loyalty and solidarity, are essential for explaining individuals' behaviour [START_REF] Arrow | Political and economic evaluation of social effects and externalities[END_REF][START_REF] Boyer | Comment émerge la coopération. Quels enseignements des jeux évolutionnistes[END_REF] 13 . To sum up, whereas bilateral enforcement logically emphasises strict economic incentives or selfish motivations, structural enforcement stresses the importance of both selfish and unselfish motivations.

"Insert figure 2"

Similarly, on the NASDAQ, market makers act inside a social structure, a "professional network" [START_REF] Bowles | Social capital and community governance[END_REF] where a chain of trust underpins the accomplishment of any 11 For a presentation of the operation of the two kinds of enforcement in social networks, see [START_REF] Guennif | From bilateral enforcement to structural enforcement in economic exchange[END_REF]. 12 In the same vein, Kandori describes "community enforcement": "dishonest behaviour against one partner causes sanction by other members in the society" (1992: 63). This "community enforcement" also prevails for peers that do not sanction the defector (64). Structural enforcement is also defined as "community governance" or "network governance" [START_REF] Bowles | Social capital and community governance[END_REF][START_REF] Jones | A general theory of network governance: exchange conditions and social mechanisms[END_REF]. 13 Analysing industrial districts, Saglio reveals how individuals observe a set of social rules that contains economic rules (1991, p. 531). Studying industrial vertical disintegration in Japan in the 60s and 70s, Dore notes that subcontracting relations involve both "benevolence and self-interest" (1983, p. 170). Hirschman insists on "sweet trade". According to him, trade is communication based on closed contacts among people who make promises, trust each other, claim and complain (1984, p. 69). Williamson admits that social norms such as ostracism sustain transactions. They limit self-interest, "individual aggressiveness" (1975, pp. 106-107).

transaction and where both selfish and unselfish motives operate14 . A market maker A 2 agrees to exchange with another market maker B because he chooses to trust him. He does so in order to increase his gain and obtain a higher compensation. A 2 assumes that B will follow informal rules such as a price convention or a quantity convention because these non-competitive conventions may increase market markers' compensation. Nonetheless, he assumes that if B defects and decides not to follow such conventions, he will never receive this compensation. B's defection will impose losses on A 2 .

In addition, A 2 trusts B because he assumes that the A i adhere to certain common rules:social norms15 . More precisely, individuals do not respect common rules unconditionally, following what Granovetter calls an over-socialised view of action. Collectively, players define and use social mechanisms expecting that most of the time these mechanisms will work to their advantage and only sometimes impose costs on them 16 . A 2 anticipates that peers will punish B if he defects. B will be subjected to harassment and above all, he will be ostracised. The A i will impede B's access to network information and other tangible and intangible resources. Thus, maverick market makers who often improved the best quote would not get an execution. This refusal to trade is known as being "traded through". Maverick market makers were also subject to "backing away" and "being made last call" by other market makers. "Backing away" involved the failure of one market maker to honour its posted quote to another market maker, as required by SEC and NASD rules. Being made "last call" involved only trading with the maverick market maker when the market began to turn against the maverick, or when a market maker had no other alternative but to trade with him. Victim of one of these sanctions, defector B will not increase his compensation.

As a result, the market makers followed the price convention, quoted large dealer spreads and increased their profit at the expense of their customers. The price convention limited the flexibility and competitiveness of price quotations in the NASDAQ Stock Market.

Discussion

We intend to develop a theoretical contribution to embeddedness based on game theory tools. The passage from the bilateral enforcement described by standard economic theory to structural enforcement throws light on the influence of social structures. Reputation is one of the mechanisms that underpin the accomplishment of spot-market transactions. As individuals are not astructural, social norms or common rules underpin every transaction. Using this theoretical approach, we can describe the way the NASDAQ social structure in the mid-eighties influenced market makers' behaviour and induced non-competitive practices.

A few days after the publication by the Wall Street Journal of a paper presenting the findings of [START_REF] Christie | Why did NASDAQ market makers stop avoiding oddeighth quotes?[END_REF], four prominent NASDAQ stocks previously quoted only in even eighths, suddenly began to be quoted in both even and odd eighths [START_REF] Smith | The NASDAQ Stock Market: historical background and current operation[END_REF]. In 1996, the publication of the US SEC and DOJ investigation reports put an end to the price convention and other non-competitive practices. The conclusions of these reports brought about two major reforms of the NASDAQ market organisation.

Firstly, the Rudman Commission (SEC, 1996) recommended more separation between the regulatory objectives of the NASD and the organisation/competitive objectives of the NASDAQ. A new subsidiary, NASD regulation, Inc., was founded and began operating in February of 1996 in order to promote fair representativity within the NASDAQ market's board of directors. At the time, in 1994, the board of directors was in majority composed of representatives of market maker firms.

Secondly, the SEC adopted the "Order Handling Rules" (OHR) intended to change the way the NASDAQ operates. The first component of the OHR is the Limit Order Display Rule (SEC Rule 11Ac1-4). This rule stipulates, for all NASDAQ securities, that the public limit orders17 should be reflected in the Best Bid and Offer disseminated by the market. The second component of OHR is new amendments to the Quote Rule prohibiting market makers from placing one quote in NASDAQ and a different one in an Electronic Communications Network (ECN). The OHR applies principles associated with agency auction markets to a quote-driven dealer market [START_REF] Smith | The effects of Order Handling Rules and 16ths on NASDAQ: a crosssectional analysis[END_REF]. It introduces competition between market maker quotes and public limit orders, and contributes to narrow spreads. Today, although collusive practices have not completely disappeared because of the reforms, they nevertheless only affect a very low volume of transactions and few stocks. However, some "courtesy" practices such as "preference trading" remain. According to this practice, brokers and market makers are allowed to direct or "preference" an order to any market maker who agrees in advance to execute orders at the best-quoted prices, regardless of the price actually quoted by the market maker to whom the order is directed [START_REF] Christie | Why did NASDAQ market makers stop avoiding oddeighth quotes?[END_REF][START_REF] Godek | Why NASDAQ market makers avoid odd-eighth quotes[END_REF]. Market makers may "direct trades based on non-price considerations, such as established business relationships" (Godek, 1996, p. 466) 18 .

As a final point, it is important to underline the fact that social structures do not only produce non-competitive practices. They may also generate social rules which represent important lubricants for the functioning of the market [START_REF] Arrow | The limits of organization[END_REF]. Although they are competitors, market makers frequently need to trade with one another. For instance, a market maker may call on another market maker's services in order to reduce the risk related to a short position. When a trader sells stocks that he does not own, he can ask another trader to sell him these stocks to balance his position. These social rules help to introduce more flexibility in market markers' operations without being detrimental to investors' interests. In fact, investors can buy or sell stocks without delay. Ultimately, the social structure improves the fluidity of the market's functioning.

Fig

  Figure 1. "Chain of trust" in a transaction between A 2 and B

Since 1985, several authors have proposed a view of embeddedness and described the way social structures influence individuals' behaviours in ways neglected by standard economy theory[START_REF] Zuckin | Structures of Capital: The Social Organization of the Economy[END_REF][START_REF] Uzzi | The sources and consequences of embeddedness for the economic performance of organizations: the network effect[END_REF][START_REF] Gulati | Where do inter-organizational networks come from?[END_REF]

2000).

In a dealer's market, the market makers or dealers offer bid and ask prices continuously. The alternative organisation is an order-driven market where the prices are determined by the confrontation between the buyers' orders and the sellers' orders.

Although the NASD is a Self Regulation Organisation, it is still under the control of the SEC.

The Department of Justice conducted numerous telephone and in-person interviews of current and former NASDAQ stock traders and investors, and listened to approximately 4500 hours of audiotapes of telephone calls between stock traders employed by the defendants and other market makers. It also analysed data showing all market makers quote changes on NASDAQ during a twenty-month period between December 1993 and July 1995.

Recently, US equity markets have moved to decimal quotations.

Similarly,Breton and Wintrobe (1986) claim that trust results from belief formulations in repeated transactions. The perspective of future gain motivates ex-post good behaviour and legitimates ex-ante trust between players[START_REF] Meidinger | Confiance, Réciprocité et Cheap Talk[END_REF].

Given their appurtenance to standard economic theory and its under-socialised view of economic behaviour, Granovetter argues that the reputation models proposed by game theorists are useless for capturing the essence and effective influence of embeddedness(1985, p. 490).

The balance between selfish and unselfish motivations is also presented as a particular trade-off between competitive and cooperative behaviours within industrial districts, networks or communities(Piore and Sabel, 1984;[START_REF] Bernstein | Opting out of the legal system: extralegal contractual relations in the diamond industry[END_REF][START_REF] Gulati | Where do inter-organizational networks come from?[END_REF]).

Sociological studies on financial markets shed light on the role of the network[START_REF] Baker | Floor trading and crowd dynamic[END_REF], the role of the exchange organisation[START_REF] Abolafia | Structured anarchy: formal organization in the commodities futures markets[END_REF] or the role of local norms[START_REF] Hassoun | Trois interactions hétérodoxes sur les marchés à la Criée du Matif. Rationalité locale et rationalité globale: une relation non contradictoire?[END_REF].

A market maker admitted that in the absence of the price convention and in certain instances, he would have used odd-eighths quote increments (US SECReport, 1996).

Public Limit Orders are posted by the investors in an order-driven auction market and specify a price and a quantity.

This kind of procedure is facilitated, ceteris paribus, by the specific NASDAQ organisation of exchanges[START_REF] Revest | La nature sociale des marchés financiers : le cas du NASDAQ[END_REF]. For example, unlike the NYSE, the NASDAQ and other dealer markets do not have time priority rules requiring market orders to be executed with the entity who first posted the current best quote(Grossman et al.,

1997).