Damien Besancenot

Habib Dogguy

Habib Dogguy Paradigm

Shift 2011 Halshs-00590527v3

Paradigm Shift

Keywords: Paradigm shift, Scientific choice, Research dynamics, Mean field game. JEL Classification : O39, C61

This paper analyses the consequences of young researchers' scientific choice on the dynamics of sciences. We develop a simple two state mean field game model to analyze the competition between two paradigms based on Kuhn's theory of scientific revolutions. At the beginning of their career, young researchers choose the paradigm in which they want to work according to social and personal motivations. Despite the possibility of multiple equilibria the model exhibits at least one stable solution in which both paradigms always coexist. The occurrence of shocks on the parameters may induce the shift from one dominant paradigm to the other.

During this shift, researchers' choice is proved to have a great impact on the evolution of sciences.

Introduction

Social sciences, among other disciplines, are consistently subject to conceptual or methodological swings. In economics for instance, Transaction Costs analysis gave way to Agency Theory, Endogenous Growth appeared at the expense of standard Growth theory and, more recently, Behavioral Finance deeply challenged the standard Market Efficiency Hypothesis. Such an evolution suggests the existence of life cycles affecting research agendas or of paradigm shifts, a core concept developed in [START_REF] Kuhn | The strucutre of scientific revolution[END_REF].

1

In a broad sense, a paradigm may be defined as a set of theories and empirical methodologies which allow a scientific community to identify frame and solve problems and serve as a foundation for future scientific discoveries. During periods of normal science, a paradigm allows reporting interesting or surprising findings and will remain dominant as long as it can stay attractive for the large majority of researchers. While this paradigm attracts the majority of scientists, two kind of academic fields are unlikely to attract a vast amount of researchers [START_REF] Crane | Fashion in science : does it exist? Social Problems[END_REF]. They are either new topics for which the theoretical implications are not fully realized (pre normal science) or traditional research fields for which the immediate intellectual content has been exhausted and only remains difficult theoretical problems which are not really attractive for young researchers (post normal science). During a paradigm shift two simultaneous changes are supposed to occur: the decline of the old paradigm, when the paradigm begins to fail solving problems and explaining anomalies and the emergence of a new one if a new theoretical corpus allows the publication of promising results. During these changes, the hope of new discoveries modifies the researchers' scientific choices who progressively abandon the traditional research fields in favor of the new set of assumptions.

Driven first by scientific considerations, the paradigm shift also appears as a social fact involving the complete community of scientists. During crisis, the increase in the number of researchers involved in the new scientific approach induces a social phenomenon which will cumulatively foster its attractivity. More researchers in an academic field simultaneously increases the potential audience of a given research, rises the ease in finding efficient co-writers, guarantees an easier access to publication mediums and contributes simplifying the funding of research. The increase of the scientific community interested in a scientific field thus influences -per se -the researchers' scientific choice. When the new set of assumptions attracts most of a new generation of scientists, the older school disappears. Researchers who stay working in the old school see their influence decreasing and their contribution are rapidly marginalized.

Demographic elements also contribute to the dynamics of science. History of sciences gives various illustrations to the fact that the retirement of one generation of elite scientists and their replacement by a new generation allows the latter to develop more easily new theories or approaches [START_REF] Barber | Resistence by scientists to scientific discovery[END_REF].

Besides, one cannot neglect the stimulus brought to researchers through paradigm competition. According to [START_REF] Kuhn | The strucutre of scientific revolution[END_REF], "Competition between segments of the scientific community is the only historical process that ever actually results in the rejection of one previously accepted theory or in the adoption of another ". During periods of normal science, opponents to the dominant approach highlight the existence of anomalies which seem inconsistent with the leading paradigm. In answer, supporters of the paradigm spend a large part of their career in the process of puzzle solving, an activity which allows to comfort the established framework. Paradigm competition appears as one additional driving forces of scientific productivity.

This paper aims at considering the various determinants of the researchers' choice of their scientific issue and the consequences of these choices in the general evolution of science. If this approach clearly deals with various aspect of Khun's work, we do not claim to formalize his theory. Our purpose is to focus on the various conditions that could contribute to the decline of a paradigm and the shift to a new one. In this purpose, we build a highly stylized mean field game closely related to the description by [START_REF] Guéant | Théorie des jeux à champs moyens et applications économiques[END_REF] of the workers' choices in a two sector economy.

In the paper at hand, we consider an economy with a continuum of researchers and two competing paradigms. Researchers produce homogeneous papers according to a production function which reflects both the development stage of the paradigm in which the scientists are involved and the repartition of the researchers among the two paradigms. At each point in time, a fraction of researchers quit academia and is replaced by an equivalent number of young researchers. Each of them has to choose in which paradigm he or she wants to carry out his or her work. Two factors motivate the choice of these young researchers at the beginning of their career: the intertemporal remuneration scheme (social or monetary) and the personal preferences.

A priori, the young researchers' scientific choice is firstly influenced by their affinity with the topic that they will handle for the rest of their life. They will choose between the various scientific topics according to their taste, given their attitude to risk, their greater or lesser reluctance to treat opened up questions or their desire to engage in riskier issues [START_REF] Alon | How to choose a good scientific problem[END_REF]. However, in their choice, young scientists cannot ignore the influence of the remuneration scheme offered by each of the two paradigms. As any scientist, a young researcher seeks social recognition [START_REF] Merton | Priorities in scientific discovery : a chapter in the sociology of science[END_REF], a recognition which comes with the publication of new results and is dramatically linked to the possibility of creating and disseminating new knowledge [START_REF] Stephan | The economics of science[END_REF]. Besides, monetary wages are also highly related to the academic resume and the individual scientific production (see for instance diamond swidler) In turn, as this scientific production is influenced by the proportion of researchers working in the same paradigm, the dynamics of the population distribution between the two paradigms has a crucial influence on the young researchers' choice.

According to the initial values of the parameters, the model exhibits one or two stable equilibriums. In each equilibrium, the two paradigms always coexist; one paradigm is dominant attracting the majority of the researchers while the other is dominated. In these equilibriums, coexistence is due to the voluntary choice by some young researchers of a research agenda in the dominated paradigm even if this agenda is not intended to lead to major innovation.

When the model allows for two stable equilibriums, the equations give no indication about which of the two competing paradigms should become predominant. Both paradigms could possibly become dominant and the hierarchy is inherited from history of the scientific field which drove to the initial repartition of the researchers among the two paradigms. In this case, a paradigm shift may occur if random shocks on some of the parameters value contribute to eliminate the dominant paradigm as a stable equilibrium. After such shocks, the vast majority of young researchers will be attracted by the new paradigm which allows for a rising remuneration as long as the number of researchers involved in the paradigm increases.

While analyses of the dynamics of sciences belong now to a well established field of research in economics, there are only few theoretical analyses that offer a formal model of paradigms evolution. As a related work, we can refer to Sterman and Wittenberg (1999) who provide a Kuhnian dynamic model in which paradigm changes are conditioned by positive feedback loops. [START_REF] Besancenot | Paradigm depletion, knowledge production and research effort[END_REF] worked out a hierarchical differential game between editors and authors.

The production of scientific knowledge is analyzed as the extraction of potential knowledge from a paradigm seen as an exhaustible resource. Editors can accelerate or slow down knowledge production and paradigm depletion may occur when editors allow for a fast rate of knowledge extraction. In this model, paradigm depletion may be an optimal outcome. More recently [START_REF] Bramoullé | Research cycles[END_REF] developed an overlapping generation model in which researchers allocate their working time between old or new fields of research in order to maximize the authors' reward. At each period, one paper published in a given paradigm yields both a citation premium increasing with the future number of contributions to the paradigm and a direct remuneration linked to the intrinsic value of the paper. The model exhibits solutions with various properties according to the values of the parameters. In some cases, the model allows for succession of periods of emergence of new paradigms and periods of exploitation of the old ones. In other cases, sunspots may occur where expectations of a high payoff in investment in a scientific field attract lots of researchers in the paradigm and allows for self-fulfilling expectations. Among the literature, our model presents a greater affinity with the work of [START_REF] Brock | A formal model of theory choice in science[END_REF] who developed a model in which researchers' scientific choice is made by reference to conformity.

Their model puts a special emphasis on the tendency for individual scientists to place a greater weight on theories accepted by the majority of the academic community. 1 Under this assumption, the authors put forward a multiplicity of equilibriums and the possibility of jump from one equilibrium to the other in case of shock on the parameters. Our approach differs from this work in three ways. First we develop a model in which the arguments of the scientific choice are directly linked to the scientific reward scheme. In their choice, researchers perfectly take into account the future possibilities of papers production and the social and monetary rewards that come with the academic resume. Second, our model allows taking into account the demographic dimension of the problem and its influence on the paradigm shift. Third the model is built on the mean field game approach introduced by Lions and Lasry (Lasry andLions, 2006a,b, 2007), see also [START_REF] Guéant | Théorie des jeux à champs moyens et applications économiques[END_REF] for a thorough presentation. In order to formalize the behavior of a continuum of rational agents, the Mean Field Game Theory assumes each agent to be influenced by the mean field made of the distribution of other players' behavior and considers the consequences of each individual decision on this mean field 2 . In a standard Mean Field Game, the dynamics of 1 Another topic close to this work deals with the occurrence of fads or cascades effects in sciences [START_REF] Sunstein | On academic fads and fashions[END_REF][START_REF] William | The constant causes of never ending faddishness in the behavioral and social sciences[END_REF] and among others the paper of [START_REF] Abrahamson | Necessary conditions for the study of fads and fashion in science[END_REF] in the special issue of the Scandinavian Journal of Management dedicated to this subject.).

Obviously, a fad may occur when people decide to do something just because other people are doing it. Fads effects are closely related to the conformity effect studied in [START_REF] Brock | A formal model of theory choice in science[END_REF].

2 The Mean Field Game Theory adopts the methodological of statistical physic while modelizing the interaction of a great number of particles. Faced to this insurmountable computa-

the system is governed by two equations: a backward Hamilton-Jacobi-Bellman equation describing the optimal behavior of agents given the distribution of the other players and a forward Kolmogorov equation which takes into account the influence of each player on the mean field. The Nash equilibrium of the game appears as the solution of these two equations. In this paper, we consider a simplified model based upon a system of ordinary differential equations while keeping the same characteristics.

The paper is organized as follows. Section 2 introduces our main assumptions about the researcher's payoffs, their productivity and the dynamics of the model given the young researchers' choice. Section 3 presents the properties of the equilibriums. Section 4 provides a numerical simulation of the model for various values of the parameters and section 5 discusses the results in terms of paradigm shifts. A last section summarizes our conclusions

Basically, this choice depends on the researchers' reward structure which includes two different items: an intrinsic remuneration linked to the researcher's affinity with his research agenda, and an extrinsic one which results from his research activity.

Researchers extrinsic remuneration

The extrinsic reward of an academic work is composed of two different elements :

a social remuneration linked to the interest paid by the scientific community to the researcher's work and a financial reward, typically the salary of the researcher. These elements will be formalized through three main variables:

• Let us denote by Q i (t) the number of papers published at date t by a representative i-researcher (papers quality is assumed to be homogeneous and Q i (t) also gives a qualitative measure of the scientific production of the i -researchers). According to [START_REF] Merton | Priorities in scientific discovery : a chapter in the sociology of science[END_REF], the scientific community awards recognition for being the first to communicate a new knowledge.

Publication, which is a necessary step in establishing priorities, thus appears as a proof of efficiency and the larger the number of publications in an academic resume the higher the peer social recognition [START_REF] Stephan | The economics of science[END_REF]. Moreover, the financial part of the researchers' reward is largely influenced by his/her academic resume. The role played by the number of publications or citations in an academic career has largely been documented in the academic literature [START_REF] Hamermersh | Scholarship, citations and salaries: Economic rewards in economics[END_REF][START_REF] Diamond | What is a citation worth[END_REF] or [START_REF] Swidler | The value of a finance journal publication[END_REF]). Hereafter, social and monetary rewards will thus be assumed increasing with Q i (t).

• Let N i (t) denote the number of i -researchers at date t. Obviously, the greater the population of researchers potentially interested in a scientist's work, the more his / her work will be used or cited and the larger will be his scientific reputation. Thus, the researcher's social reward involved in the paradigm i is increasing with N i (t).

• Define by m i the institutional component of the researchers' reward. As public or private funding agencies may want to promote one paradigm, they may offer special subsidies to researchers involved in this field of research. In the paper at hand, m i ∈ [1, ∞[ measures the level of these monetary incentives. When m i = 1, funding agencies provide no incentive for researchers to work in the scientific area i. For m i > 1, the higher is m i and the higher are the incentives to become a i-researcher.

Finally, the instantaneous value, ω i (t) , of the researchers' extrinsic remuneration (social and monetary) appears as a function of the previous variables:

ω i (t) = ω i (m i , N i (t) , Q i (t)),
and, at date t the intertemporal expected remuneration for an i -researcher is given by:

u i (t) = E t+T t ω i (m i , N i (s) , Q i (s)) e -α(s-t) ds
here T is a random variable that corresponds to the time spent in the research field i by an i-researcher during his academic life. Assuming that this variable follows an exponential law of intensity λ, this last expression takes the simplified shape:

u i (t) = ∞ t ω i (m i , N i (s) , Q i (s)) e -(α+λ)(s-t) ds.
(1)

Specific assumptions

In order to obtain tractable solutions, the i -researcher 's production function will be formalized through a classical CES function4 :

Q i (t) = (a i N r i (t) + (1 -a i ) (N -i (t) Q -i (t)) r ) 1/r . (2)
where:

1. N i (t) is the number of i-researchers.

2. N -i (t) is the number of researchers in the competing paradigm. As the continuum of researchers is of size one, we have The rationale behind such a function is straightforward. Other thing remaining the same, an i-researcher's productivity is fostered by the number N i (t) of researchers involved in the same paradigm. More researchers means more conferences in which one can receive critics about his work and discuss with other academic fellows the new scientific developments of he paradigm. More researchers involved in a scientific field also means more opportunity of collaborations which increase productivity (see for instance [START_REF] Mcdowell | The determinant of coauthorship : an analysis of the economic litterature[END_REF], [START_REF] Landry | An econometric analysis of the effect of collaboration on academic research productivity[END_REF] or [START_REF] Abrahamson | Necessary conditions for the study of fads and fashion in science[END_REF]) and induces a greater number of reviews in which one can publish his/her work [START_REF] Stigler | The journals of economics[END_REF].

N -i (t) + N i (t) = 1. 3. N -i (t) Q -i (t)
Besides, competition between paradigms plays a crucial role on scientific productivity. During periods of normal science, while opponents to the dominant approach highlight the existence of anomalies which seem inconsistent with the leading paradigm, supporters of the paradigm spend a large part of their career to comfort the established framework. In economics, a good illustration of such a phenomenon can be found in the evolution of the efficient market hypothesis in reaction to the systematic research of anomalies in the financial market by supporters of behavioral finance [START_REF] William | Handbook of the Economics of Finance, volume 1, chapter Anomalies and market efficiency[END_REF].

This opposition is formalized by the specific constant a i which captures the intrinsic dynamism of the paradigm i and its stage in the paradigm shift. From its rise until its decline, a paradigm's life is subject to random shocks that affects its relation vis-vis its competitor. In the early years of the new paradigm i, some researchers are disappointed by the results of the dominant concepts and start pursuing alternative topics or methodology in the hope that a new set of tools or assumptions would bring better results. At this stage, the new approach defines itself by opposition to the dominant paradigm and a i is rather low. However, a shock on a i can occur if the new set of assumptions starts allowing to report interesting or surprising findings. In such a case, a i increases as authors become more interested in the development of the new results than by the criticism of the old ones. Finally, a i may decrease when the most important problems of the field are solved or proven to be unsolvable. In this case, new papers in the field bring fewer innovations and researchers will spend most of their time trying to answer the critics raised by the competing paradigm.

Finally, we assume that the instantaneous remuneration for a i -researcher presents a multiplicative shape and is given by:

ω i (t) = m i N i (t) Q i (t) (3)

Intrinsic remuneration and the young researchers' choice

At the beginning of his academic life, each researcher has to choose the sector in which he/she will work for the rest of his/her life. In this choice, the remuneration offered by each field of research plays a determining role; however, the young researchers will also take into account their personal preferences among the various academic fields [START_REF] Alon | How to choose a good scientific problem[END_REF], [START_REF] Stephan | The economics of science[END_REF]). In this paper, the researcher's preferences which induce his/her intrinsic remuneration are modeled by a random variable µ which measures the value for a young researcher of building his/her career in the first scientific area. By assumption each researcher is characterized by his/her own µ, and this value is distributed over the researchers' population according to a standard normal law.

When the two research agendas bring the same intertemporal remuneration u 1 (t) = u 2 (t), Cf. Eq. ( 1), a researcher will choose the first paradigm for any µ positive and the second one for a negative µ. When the intertemporal remunerations exhibit significant differences, a young researcher may nevertheless choose the less remunerative if he/she exhibits strong preferences for this field of research. Formally, the decision rule for a young researcher will be to choose the first area if and only if 5 :

u 1 (t) + µ ≥ u 2 (t) . ( 4
)
Let us reason on an infinitesimal interval [t, t + dt]. According to the previous assumptions, during this time period a proportion λdt of researchers retires both 5 We made the assumption that the young researchers have perfect forseight.

We linearize the system in the neighborhood of each stationary solution

(N * 1 , ∆u * ). dN1 dt (t) = -λN 1 (t) + λ∆u (t) F (∆u * ) d∆u dt (t) = (α + λ) ∆u (t) -[∂ 1 ω 1 -∂ 2 ω 2 -∂ 1 ω 2 + ∂ 2 ω 2 ] (N * 1 , 1 -N * 1 ) N 1 (t)
In order to determine the nature of the stationary solution, we have to study the eigenvalues of the following matrix :

M = -λ λF (∆u * ) -[∂ 1 ω 1 -∂ 2 ω 2 -∂ 1 ω 2 + ∂ 2 ω 2 ] (N * 1 , 1 -N * 1 ) α + λ Proposition 3
The only trajectory compatible with the terminal condition on ∆u is the trajectory that converges towards the saddle point.

Proof. Imagine that the terminal condition is verified on a trajectory that diverges. Since ω i is bounded there exists C > 0 such that ∀N ∈ [0, 1],

|ω 1 (N, 1 -N ) -ω 2 (N, 1 -N ) | ≤ C, hence ∆u (t) = ∞ t ω 1 (N 1 (t) , 1 -N 1 (t)) -ω 2 (N 1 (t) , 1 -N 1 (t)) e -(α+λ)(s-t) ds ⇒ |∆u (t) | ≤ ∞ t |ω 1 (N 1 (t) , 1 -N 1 (t)) -ω 2 (N 1 (t) , 1 -N 1 (t)) |e -(α+λ)(s-t) ds ⇒ |∆u (t) | ≤ C ∞ t e -(α+λ)(s-t) ds ⇒ |∆u (t) | ≤ C α + λ
But, by assumption, lim t→∞ |∆u (t) | = +∞. This is absurd then this trajectory is not compatible with the terminal condition on ∆u.

Numerical simulations

We have seen above that the differential system admits stationary solutions but the number of these solutions depends upon the value of the variables a 1 , a 2 , m 1 and m 2 . In this section, we consider two important cases presented in table 1 .

We are going first to study in each case the stationary system and then turn to the nature of these stationary solutions. Hereafter, we will take r = 0.25. We recall that the stationary solutions are given by:

     N 1 * = F ω 1 (N * 1 , 1 -N * 1 ) -ω 2 (N * 1 , 1 -N * 1 ) α + λ ∆u * = ω 1 (N * 1 , 1 -N * 1 ) -ω 2 (N * 1 , 1 -N * 1 ) α + λ case a 1 a 2 m 1 m 2 Number of stationary solutions Case 1 0.5 0.5 1 1 3 Case 2 0.2 0.6 1 1 1 Case 3 0.6 0.2 1 1 1 1 1.5 3 Table 1: Table of parameter value

Case 1

See Table 1 for the data of the problem. We first resolve the fixed point problem of Proposition 2. In Figure 1 we plot the graph of the identity function on [0, 1] and the function

N 1 → F ω 1 -ω 2 α + λ . It

Case 2

See Table 1 for the data of the problem. In this case a 1 < a 2 . The unique fixed point is equal to N * 1 = 0.0083 as shown in figure. The stationary solution of the system is a saddle point since the determinant of the matrix M is equal to -0.0047. Table 3: Dynamical properties of stationary solutions

Case 3

See Table 1 for the data of the problem. In this example a 1 > a 2 . When m 1 = m 2 = 1, the system admits a unique fixed point equal to N * ,3 1 = 0.9916. Hence the unique stationary solution of the system is N * ,3 1 = 0.9916 and ∆u * = 2.3953.

This solution is a saddle point since the determinant of the matrix M is equal to -0.0047 and it leads to a domination of the first paradigm. The institutional factor may change considerably the dynamic properties of the system as shown in figure 3. When m 2 = 1.5, there exist three stationary solutions as represented by the dashed curve. The results are summarized in table 3. Whatever the case considered in the previous section, the two competing paradigm always coexist. However, in the stable equilibriums the academic landscape is asymmetric by nature. One scientific approach appears as dominant, attracting a large majority of the researchers, while the other one, clearly dominated, is minority. Coexistence is guaranteed in this equilibrium because each paradigm is the complement of the other. The dominant field of research is stimulated by the researchers' critics from the competing research field while these researchers find easily matter of criticism in the massive scientific production of the dominant paradigm. Note that, in case 1, the two paradigms could potentially be dominant. The hierarchy between the two paradigms is then only due to historical choices of past researchers who mostly chose one of the two paradigms.

As the equilibrium is stable, this paradigm may stay dominant for long.

In this model, paradigm shifts may appear as the consequence of successive and unanticipated shocks on the relatives values of a i .7

During periods of normal science, researchers only focus on the development of the dominant paradigm (hereafter paradigm 2). Results are considered as significant when they add to the scope and the precision with which the paradigm can be applied and, in these settings, puzzle solving is the best way to increase the generality of the paradigm. Researchers are mainly interested in the improvement of the assumptions, the procedures or of the generality of the results inside the paradigm; a 2 is close to one. In such a period, results from the dominated field of research are neglected in the scientific debate and researchers involved in these topics have to define themselves by opposition to the dominant paradigm. In this case, with a high a 2 and a low a 1 , the equilibrium is described by figure 2.

Apparition of anomalies brings an important shock to the model and changes the nature of the equilibrium. As more and more puzzles appear inconsistent with the dominant concepts, young researchers start pursuing alternative topics or methodology in the hope that a new set of tools or assumptions would bring better results. New possibilities of analysis are considered by these authors who start studying these problems with a greater autonomy, a 1 rises. In the same time, researchers from the dominant paradigm have to spend more time to address the critics of their challengers: a 2 drops. Under our specific assumptions this implies a lower number of publications in the dominant field and a slide in the social and monetary remuneration for researchers involved in this paradigm.

In the other field of research, the opposite effects are at work and this field becomes more attractive for young researchers. When a radical change affects a 1 and a 2 , the model can reach the situation described by the continuous curve of Case 3. In this situation, the model presents a unique stable equilibrium in which the old paradigm leaves its place to a new dominant one. The paradigm shift occurs according to an adaptation process from the old equilibrium to the new one. During this shift, the number of researchers attracted by the new topics raises continuously as young researchers is attracted in a cumulative way by the new remuneration schemes. Greater social recognition and higher wages are both the incentives that attract the young scientists in the new paradigm and the consequence of this massive attraction. At the end of the adjustment process, a new steady state is reached in which proponents of the old paradigm remain active -but with a minority status.

Note that the paradigm shift may also be caused or hindered by public policy.

Indeed, goverment may choose to consolidate the dominance of one paradigm, for instance paradigm2, by funds and other types of support (interpreted here by an increase of the institutional factor m 2 ). This policy can be seen as justified in period of normal science and may last as long as the dominant paradigm presents no failure, but if new puzzles appear and empirical anomalies challenged its theoretical implications then policymakers face two choices : ignoring these anomalies and maintaining the same policy, described by the dashed curve of figure 3 where the equilibrium is N * 1 or abandoning the dominant paradigm and stop supporting it which lead to a paradigm shift and a new equilibrium as described by the continuous curve of figure 3.

conclusion

The two state mean field games developed in this paper models the competition between two paradigms in an academic field. The model accords a central role to the young researchers' choice in the dynamic of science. Researchers have perfect foresight and choose their scientific field according to their own tastes and given the intertemporal rewards provided by the two competing paradigms.

Three major insights emerge from the model. First, for any set of parameters, there always exists stable steady state equilibrium. In this equilibrium, both paradigms coexist in a hierarchical order. Second, changes in the reward schemes are able to challenge this hierarchical order. An increase in the productivity in one paradigm or the implementation of incentives in favor of one of the two paradigms clearly contributes to the reinforcement of this set of assumptions and tools. Moreover, when young researchers observe a decline in the activity within the dominant paradigm, they anticipate the end of the period of normal science which motivates them to look for others concepts or methods to treat the anomalies. Third, for important shocks on the parameters, the equilibrium with the dominating paradigm may disappear. In this case, one can observe a paradigm shift with the progressive replacement of former major scientists involved in the old paradigm by new generations of researchers, an increasing share of which choosing the new paradigm.

In our model, a paradigm shift appears as the consequence of two kind of unpredictable chocks. A chock in the scientific production functions may modify the interaction between the paradigms And favor one paradigm at the expense of the other. If a research agenda allows for an increase in the productivity of its researchers, the associated private and social rewards will rise and its scientific attractiveness will be enhanced. The institutional factor may also play a dramatic role in the choice of junior researchers and consequently in establishing a new hierarchy between paradigms. A government can foster the paradigm shift by providing temporary incentives to young researchers choosing the publicly encouraged set of assumptions. If these incentives reach a given threshold, the former equilibrium may disappear and the convergence to the new paradigm will be self-sustaining. After some adjustment in the relative number of researchers involved in the two paradigms, the incentive may be removed without questioning the paradigm shift.

In order to keep the analysis tractable, this paper is built on some restrictive assumptions. For instance, the model considers that young researchers make a definitive choice at the beginning of their academic life; future work should consider the possibility of a radical revision of a researcher's research agenda.

Moreover, in order to obtain an analytical characterization of the equilibrium solution, some specific assumptions have been made about the reward structure and the functional forms of the academic production. These assumptions may be questioned in order to assess the accuracy of the model. Despite its limitations, the model is interesting as it allows stressing the role of the reward scheme in the dynamic of science and gives an overview of possible applications of mean field games.

  measures the number of papers published within the competing paradigm.4. a i is a specific constant measuring the dependence of paradigm i with respect to its rival. A high level of a i reveals an autonomous field of research in which researchers are poorly influenced by the scientific activity of the other field.

  Figure 1: Case 1

  Figure 2: Case 2

  Figure 3: Case 3

The modelWe consider an academic world made up of a continuum of researchers of size 1. Each researcher practices his/her skills in one of the two available paradigms. Hereafter, a researcher working in paradigm i will be referred to as an i -researcher. Except for their preferences, researchers are assumed to be homogeneous.At each point in time, a fraction λ of the researchers quit the academic world (through volunteer departure, or involuntarily through retirement or death) and is replaced by an equivalent number of young researchers. Young researchers have then to decide in which paradigm they want to carry out their research.This decision is definitive

.tional problem, physicists consider each particules as being influenced bt a "mean field"exerted by all other particles while simultaneously taking into account the influence of each particle on the mean field.3The assumption that a young researcher makes a definitive choice of his/her problematic at the beginning of his/her career is purely technical. However, it perfectly matches with Khun's quotation of Max Plank : "a new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die, and a new generation grows up that is familiar with it."[START_REF] Kuhn | The strucutre of scientific revolution[END_REF], p.150. See also[START_REF] Morgenstern | Thirteen critical points in contemporary economic theory: An interpretation[END_REF] p. 1167 who writes that "the absorption of a new paradigm awaits, as a rule, a new generation" or[START_REF] Barber | Resistence by scientists to scientific discovery[END_REF] who give a careful description of the resistance by the senior researchers to scientific changes.

Under this assumption, the case N i = 0 could rise a formal problem as the production function would allow for some scientific production in the field of research i while no researcher would be involved in this specific field. In our model, however, this difficulty is avoided as the case N i = 0 is inconsistent with the equilibrium solution.

[START_REF] Kuhn | The strucutre of scientific revolution[END_REF] provides various illustrations that the decisive shocks that will affect a paradigm are hardly expected by scientists. See for instance Pauli's pessimistic correspondence about the future of physics at the very period which gives birth to Quanta's theory[START_REF] Kuhn | The strucutre of scientific revolution[END_REF]

pp. 83-84.

for sector 1 and sector 2 and a population of size λdt enters the academic world.

The proportion of new researchers that choose sector 1 is given by:

where F is the cumulative distribution function of a standard normal variable.

Finally, the system is governed by the following two equations:

Hereafter, we will use the variable ∆u = u 1 -u 2 .

From ( 1) and ( 6), we can now describe the dynamics of the model:

Proposition 1 The dynamics of the model is given by the two following equa-

with an initial condition on N 1 , N 1 (0), and a terminal condition on ∆u, lim t→∞ e -(α+λ)t ∆u (t) = 0.

Proof. Remark that the first equation of the system ( 7) and ( 6) are formally equivalent. In a same way, (7) and the terminal condition verified by ∆u are equivalent to the integral form (1) above. Indeed, after subtraction of the term (α + λ) ∆u (t) from both sides of ( 7) and multiplication by -e -(α+λ)t we get:

6

The system of differential equations presented above is very typical of mean field game.

The first equation which is forward can be identified to the Kolmogorov equation whereas the second one, backward, replaces the Hamilton-Jacobi-Bellman equation [START_REF] Guéant | Théorie des jeux à champs moyens et applications économiques[END_REF].

After integration with respect to t, and under of the terminal condition, this is equivalent to:

which finally leads to Eq.( 1):

3 Properties of the stationary solutions

Proposition 2 A stationary solution of the model is given by:

Proof. . The stationary solution verify the following system :

From these two equations we get :

)) The existence of such a solution is a simple application of the intermediate value theorem. Indeed, as

we get f (0) < 0 and f (1) > 0. This gives the result.

It now remains to study the dynamical properties of our system and the nature of each stationary solution. Let's consider the differential system without the terminal condition on ∆u : = (α + λ) ∆u (t) -[ω 1 (N 1 (t) , 1 -N 1 (t)) -ω 2 (N 1 (t) , 1 -N 1 (t))] (13)


Itziar Arrieta
email: itziar.arrieta@unavarra.esraynal@irisa.frfitxi@unavarra.esmendivil@unavarra.es

Federico Fariña

José Ramón

G De Mendívil

Michel Raynal

J.-R De Mendívil

Leader Election: From Higham-Przytycka's Algorithm to a Gracefully Degrading Algorithm

Keywords: Asynchronous system, Deterministic algorithm, Distributed algorithm, Fault-tolerance, Initial value fault, Leader Election, Message complexity, Round number. Un algorithme d' Anneau, Communication asynchrone, Election, Fautes sur les valeurs initiales

The leader election problem consists in selecting a process (called leader) in a group of processes. Several leader election algorithms have been proposed in the past for ring networks, tree networks, fully connected networks or regular networks (such as tori and hypercubes). As far as ring networks are concerned, it has been shown that the number of messages that processes have to exchange to elect a leader is Ω(n log n). The algorithm proposed by Higham and Przytycka is the best leader algorithm known so far for ring networks in terms of message complexity, which is 1.271 n log n + O(n). This algorithm uses round numbers and assumes that all processes start with the same round number. More precisely, when round numbers are not initially equal, the algorithm has runs that do not terminate.

This paper presents an algorithm, based on Higham-Przytycka's technique, which allows processes to start with different round numbers. This extension is motivated by fault-tolerance with respect to initial values. While the algorithm always terminates, its message complexity is optimal, i.e., O(n log n), when the processes start with the same round number and increases up to O(n 2 ) when all processes start with different round number values. We call graceful degradation this additional property that combines fault-tolerance (with respect to initial values) and efficiency.

Introduction

The leader election problem In the leader election problem the processes that compose a message-passing distributed system have to choose one of them to be their leader. The leader can be any of them. The fundamental property is that a single leader is eventually elected. In addition to mutual exclusion [START_REF] Raynal | Algorithms for Mutual Exclusion[END_REF], leader election is one of the most important problems of the class of symmetry-breaking problems.

It is important to observe that symmetry cannot be broken "from nothing", i.e., in systems in which processes are "identical". As an example, if all processes have the same number of neighbors in the communication graph and have no name (the system is then anonymous), there is no way to break the symmetry among processes and therefore the leader election problem is impossible to solve [START_REF] Angluin | Local and Global Properties in Networks of Processors[END_REF][START_REF] Attiya | Computing on an Anonymous Ring[END_REF][START_REF] Raynal | Communication and Agreement Abstractions for Fault-Tolerant Distributed Systems[END_REF]. Hence, we consider here that each process has an identifier and no two processes have the same identifier. Moreover, identifiers have to be usable, namely, they are totally ordered and can consequently be compared.

Election on rings: a short historical perspective The leader election problem has been introduced by Le Lann in [START_REF] Lann | Distributed Systems: Towards a Formal Approach[END_REF], which also presents a leader election algorithm for bidirectional rings whose message complexity is O(n 2 ). This result has been improved for the average case by Chang and Roberts [START_REF] Chang | An Improved Algorithm for Decentralized Extrema Finding in Circular Configurations of processes[END_REF], who designed an algorithm whose average case message complexity is O(n log n) and worst case message complexity is O(n 2 ). Then, Hirschberg and Sinclair designed an optimal algorithm for bidirectional rings, i.e., an algorithm whose message complexity is always O(n log n).

While Hirschberg and Sinclair conjectured that O(n 2 ) was a lower bound on the number of messages for election in unidirectional rings, simultaneously, independently and using distinct approaches, Peterson on the one hand [START_REF] Peterson | An O(n log n) Unidirectional Algorithm for the Circular Extrema Finding[END_REF] and Dolev, Klawe and Rodeh on the other hand [START_REF] Dolev | An O(n log n) Unidirectional Algorithm for Extrema Finding in a Circle[END_REF], disproved this conjecture by presenting election algorithms for unidirectional rings requiring at most 2n log n + O(n) messages. Then, Dolev Klawe and Rodeh improved their algorithm to obtain a 1.5 n log n + O(n) message complexity while Peterson improved his algorithm to obtain 1.441 n log n + O(n) message complexity. Applying their technique to Peterson's algorithm, Dolev Klawe and Rodeh obtained an algorithm with message complexity 1.356 n log n + O(n).

Finally, using a totally new approach, Higham and Przytycka designed an election algorithm for unidirectional rings whose message complexity is 1.271 n log n + O(n) [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF]. It is shown in [START_REF] Bodlaender | Some Lower Bound Results for Decentralized Extrema Finding in Ring of Processors[END_REF] that the message complexity of the leader election problem on a unidirectional ring is Ω(n log n). Hence, Higham-Przytycka's algorithm is optimal with respect to that complexity measure. Moreover, due to the constant 1.271, it is the best algorithm known so far when considering that criterion. However, it is not yet known which is the smallest constant c such that election can be solved on unidirectional rings with message complexity c n log n + O(n) (it is only known that c ≥ 0.69 [START_REF] Bodlaender | Some Lower Bound Results for Decentralized Extrema Finding in Ring of Processors[END_REF]).

The reader interested in election algorithms in rings, tree networks, fully connected networks or regular networks (such as tori and hypercubes) will find an in-depth investigation in Chapter 2 of Nicola Santoro's book [START_REF] Santoro | Design and Analysis of Distributed Algorithms[END_REF] (pages 99-224).

Content of the paper Higham and Przytycka's algorithm is based on round numbers and assumes that all processes start with the same round number value. More specifically, when processes start with distinct round number values, the algorithm has runs that do not terminate.

This paper considers the possibility of initial value faults, i.e., the case where the initial values of the round numbers are faulty in the sense that not all processes start with the same round number value. We are interested in a gracefully degrading election algorithm for unidirectional rings. In the context of initial value faults for the election problem, graceful degradation with respect to round numbers means the following.

• The algorithm has to elect a leader (safety property) and terminate (liveness property) whatever the initial value of the round number at each process, and

• Its message complexity has to be as good as the best known algorithms (i.e., O(n log n)) when all processes start with the same round number value ("good" initial values), but is allowed to increase up to O(n 2 ) when processes start with different round number values ("bad" initial values).

This paper presents a gracefully degrading election algorithm. Let us observe that, in our context, graceful degradation means that the processes are allowed to use more messages only when their initial round number values are faulty in the sense they are not equal. Hence, graceful degradation captures an algorithmically interesting tradeoff between the initialization of local variables and the cost of an execution measured by the number of exchanged messages. id i (-1) r i > id(-1) r : r i ← r i + 1; send (r i , id i ) (06) id i (-1) r i < id(-1) r : status i ← relaying (07) id i (-1) r i = id(-1) r : status i ← leader (08) end case (09) r > r i : status i ← relaying; send (r, id) [START_REF] Peterson | An O(n log n) Unidirectional Algorithm for the Circular Extrema Finding[END_REF] r < r i : discard the message [START_REF] Raynal | Algorithms for Mutual Exclusion[END_REF] end case [START_REF] Raynal | Communication and Agreement Abstractions for Fault-Tolerant Distributed Systems[END_REF] else if (status i = relaying) then send (r, id) end if [START_REF] Santoro | Design and Analysis of Distributed Algorithms[END_REF] end if until (status i = leader) end repeat. 2 Computing Model a) Process model: The system is made up of n asynchronous sequential processes denoted p 0 , p 1 , ..., p n-1 . The integer i associated with p i is its index. Indexes are used only from an external observer point of view in order to make the presentation simpler. Indexes are not known by processes. "Asynchronous" means that each process proceeds at its own speed, which can be arbitrary. Moreover, no process has a priori information on the way other processes progress.

A process p i has an identifier id i (id i is a constant). No two processes have the same identifier and the identifiers are totally ordered. A process initially knows only its own identifier and the fact that identifiers can be compared. Initially, a process knows neither the identifier of the other processes nor the total number of processes n.

b) Communication model: The processes are connected by a unidirectional reliable asynchronous ring on which they can send and receive messages. "Asynchronous" means that the transfer delay of each message is arbitrary, while "reliable" means that all transfer delays are finite (no message loss) and that messages are neither corrupted nor duplicated.

"Unidirectional ring" means that messages can flow in only one direction. More precisely, a process can receive messages only from its "left" neighbor on the ring and can send messages only to its "right" neighbor on the ring. Hence, the ring has a single sense of direction (the notion of "left/right" is the same for all processes [START_REF] Santoro | Design and Analysis of Distributed Algorithms[END_REF]). Hence, without ambiguity, the sender or the destination process of a message are left implicit when a process invokes operations send() or receive().

Differently from the model used in other papers (e.g., [START_REF] Dolev | An O(n log n) Unidirectional Algorithm for Extrema Finding in a Circle[END_REF][START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF][START_REF] Lann | Distributed Systems: Towards a Formal Approach[END_REF], the channels are not required to be FIFO (First In First Out).

The Algorithm

The proposed leader election algorithm is described in Figure 1. As explained below, one of its underlying principles is a priority rule based on the parity of the current round number. This priority rule has been introduced by Higham and Przytycka in [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF].

Description of the algorithm: Local variables

In addition to its constant identifier id i , each process p i manages two local variables: status i and r i .

• status i denotes p i 's current status. Namely it is a value in the set {candidate,relaying, leader}. If a process p i wants to compete to become the leader its initial value is candidate, otherwise it is relaying. It is assumed that at least one process initially competes to be the leader.

At the end of an execution, a single process p ℓ (from the candidate processes) will be such that status ℓ = leader. We assume that, when a process is elected as a leader, it sends a message on the ring to inform the other processes that it is the leader so that they locally stop their participation in the election algorithm.

• r i denotes the current round number of p i . It can be initialized to any integer.

Description of the algorithm: Behavior of a process

The aim of the algorithm is to elect a candidate process whose identifier is an extremum among the current candidates. To that end each process p i does the following. If p i is candidate, it sends a message containing the pair (r i , id i ) to its right neighbor. Moreover, if it has not yet executed the init statement when it receives a message carrying a pair (r, id), p i executes this statement before processing the message it has just received.

When a process p i receives a message (r, id) (line 01), it forwards it to its right neighbor if status i = relaying (line 12). In this case, p i was not candidate or has been eliminated from the competition before receiving that message.

Otherwise, if status i = candidate (line 02), there are three cases to consider.

• r = r i (line 04). There are three sub-cases.

-If the round number is even and id i > id or the round number is odd and id i < id (predicate id i (-1) ri > id(-1) r , line 05), p i discards message (r, id), increments its round number r i in one unit and sends a new message (r i , id i ) to its right neighbor. This message indicates that p i is still a candidate and is trying to eliminate another candidate. If p i later receives its own message from its left neighbor (hence this message will have passed through all the other processes) it will consider itself as the leader.

-If the round number is even and id i < id or the round number is odd and id i > id (predicate id i (-1) ri < id(-1) r , line 06), p i considers that id i has a smaller priority than id. Consequently, it sets status i to the value relaying. Note that message (r, id) is not forwarded. If r is currently the highest round number, there will be one message (r i , id i ) (which has been previously sent by p i ) that will cause another process p k (such that id k = id or any other process with id i (-1) ri < id k (-1) r k and r k = r) to increment r k upon receiving (r i , id i ). Since r is not the highest round number (either due to the previous case or because there already existed a message with a higher round number), (r, id) is no longer useful. Consequently, forwarding (r, id) would unnecessarily increment the number of messages involved in the algorithm execution.

The strategy used in both previous items, where the priority is defined from the parity of the current round number and the values of id i and id (the process identifier received in the message) has first been proposed by Higham and Przytycka in [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF].

In that sense, the proposed algorithm is somehow inspired by their leader election algorithm.

-If the message received by p i is such that (r, id) = (r i , id i ), then this message was generated by p i and has passed through all the processes of the ring. Process p i considers itself as the leader (line 07). As mentioned before, p i can then send a message along the ring so that the rest of processes learn which process has been elected and locally terminate their execution of the election algorithm.

• r > r i (line 09). Due to its higher round number, the received message has priority over the last message sent by p i . Consequently, p i changes to status relaying (thus being eliminated from the competition) and forwards the received message.

• r < r i (line 10). In that case, the received message is too old, and p i discards it.

It is worth noting that the execution of different actions depending on whether r > r i or r < r i (forwarding the message in the former case and discarding it in the latter case) is what allows processes to start with different round numbers. In contrast, in the solution of Higham and Przytycka [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF] round numbers are compared only to check whether they are equal or different. More specifically, in the basic algorithm presented in [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF], when a process receives a message whose round number does not match with that of the last sent message, it simply forwards it. As a result, if all processes start with a different round number the algorithm will never terminate, since messages will be perpetually forwarded around the ring. Similarly, the improved version described in [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF], which uses early promotion by distance in odd rounds and early promotion by witness in even rounds, will also suffer from non-termination if all the initial round numbers are all different from each other and even, because messages are neither discarded nor promoted to the next round.

Proof of the Algorithm

This section proves first that the algorithm is correct, i.e., there cannot be more than one process elected as leader (Theorem 1) and the algorithm always terminates its execution electing a leader (Theorem 2). Then, we show that the number of messages is upper bounded by (a) O(n log n) when the processes start with the same round number (Theorem 3) and (b) O(n 2 ) when the processes start with arbitrary round numbers (Theorem 4).

Let I = {0, 1, . . . , n -1} be the set of process indexes. The binary operators + orover I are assumed to be modulus n, i.e., for every i ∈ I, (i ± 1) ≡ (i ± 1) mod n. Given i, j ∈ I, D(i, j) is defined as the set {(i + 1), (i + 2), . . . , (j -1)}, i.e., it represents the set of indexes of processes in the ring at the right side of p i before reaching p j . Moreover, D(i, i) is well defined: D(i, i) = I -{i}.

The set of process identifiers is denoted by ID = {id i : i ∈ I}. Round numbers are assumed to belong to the set of natural numbers including 0, namely N. For the set N × ID, we define the total order relation ≻ as follows:

(r ′ , id ′ ) ≻ (r, id) ⇔ (r ′ > r) ∨ (r ′ =
Collection des Publications Internes de l'Irisa c IRISA r ∧ id ′ (-1) r ′ > id(-1) r ). In addition, (r ′ , id ′ ) = (r, id) if and only if r ′ = r and id ′ = id. The total order allows us to compare messages of the algorithm, since every message m belongs to N × ID. Furthermore, received messages can be compared with the round number and identifier (r i , id i ) of the receiving process p i .

The computation state of the distributed algorithm at any time t is a record s t (where t can be omitted when it is clear in the context) comprising the values of the variables of each process p i in the system (where s t .var i represents the value of the variable with name var at process p i at time t), as well as the messages in the communication channels s t .c[i] for every i ∈ I. Variable c[i] represents the set of messages in the communication channel connecting process p i-1 to process p i that have been sent by p i-1 but have not been received by p i yet.

Any execution of the distributed algorithm is a finite or infinite sequence of states s 0 , s 1 , . . . , s z . . ., such that each pair (s j , s j+1 ) is obtained as the consequence of executing a computation step of the algorithm at some process. We assume that in the initial state s 0 of every execution there exists a non-empty subset of processes indexes C such that ∀i ∈ C : s 0 .status i = candidate, whereas ∀j ∈ I \ C : s 0 .status j = relaying. Moreover, we write s i → s j to indicate that s i happens before s j in the sequence of reachable states.

A process p i can execute one of the following computation steps that results in the creation of a new state: either init i (the initialization described in Figure 1) or one of the possible combinations of code lines 01 and xx (where xx ∈ {05,06,07,09,10,12}). These computation steps are assumed to be atomic and weak-fair, i.e., if one of them is always enabled to be executed, it is eventually executed.

The following lemma specifies some invariant properties of the reachable states of an execution that will be useful when proving the correctness of the algorithm. Lemma 1. For every reachable state s of any execution, and any process indexes i, j ∈ I, the following properties hold:

(1) (r, id i ) ∈ s.c[j] ⇒ ∀k ∈ D(i, j) : s.status k = relaying, (2) (r, id i ) ∈ s.c[j] ⇒ s.r i ≥ r, (3) (r, id i ) ∈ s.c[j] and (r, id i ) ∈ s.c[k] ⇒ k = j.
Item (1) of Lemma 1 states that when a message (r, id i ) reaches a process p j , all processes between p i (the process that created the message) and p j must be in the relaying status, excluding both p i and p j . Its proof is straightforward, since a message with an identifier id i can be forwarded by a process with identifier id k (with id i = id k ) only if either p k was already in the relaying status or it changes to relaying before forwarding (r, id i ). Bear in mind that when a process is in the relaying status it remains forever with this status.

On the other hand, Item (2) of Lemma 1 reflects that if there exists a message (r, id i ), the current round number of the process that created that message, r i , cannot be lower than r. This is also evident, as when a process creates a message it includes its current round number, and round numbers are never decreased.

Finally, Item (3) of Lemma 1 specifies that each message is unique within the whole ring, i.e., the same message cannot exist in two different communication channels. This is because (a) each message (r, id) is created only once, since process identifiers are all different and when a process creates a new message, it does so with a higher round number than that of the last message it sent; and (b) each message is handled only once by each process.

In order to prove that the proposed algorithm is correct, we first show in Theorem 1 that there cannot be more than one process elected as leader in the execution of the algorithm, i.e., the leader is unique.

Theorem 1. For every reachable state s of any execution: ∀i, j ∈ I : (s.status i = leader ∧ s.status j = leader) ⇒ i = j.

Proof By contradiction, let us consider that s.status i = s.status j = leader with i = j. Assuming that i is the first process that changed to status leader, then there exists a previous state s ′ such that s ′ .status i = candidate and the message (s ′ .r i , id i ) ∈ s ′ .c[i] (note that (s ′ .r i , id i ) is the message that has already traveled around the ring and changes the status of p i from candidate to leader when p i receives it, with s ′ .r i = s.r i ). By Lemma 1(1), ∀k ∈ D(i, i) : s ′ .status k = relaying. Then, s ′ .status j = relaying. Since there is no transition from relaying to leader in the algorithm, the theorem holds by contradiction.

✷ T heorem 1

Apart from ensuring that the leader is unique, we must prove that the algorithm always terminates electing a leader. First, we show that there cannot exist a state during the computation such that every process is in the relaying status.

Lemma 2. For every reachable state s of any execution, ∃i ∈ I : s.status i = relaying.

Proof By contradiction, let us assume that there exists an execution and a reachable state s such that ∀i ∈ I : s.status i = relaying. Since in the initial state s 0 there is at least one process p k such that s 0 .status k = candidate, state s must happen after s 0 . Let p j be the last process in the execution that changed status from s ′ .status j = candidate to s.status j = relaying. At s ′ , there exists a message m = (s 1 .r i , id i ) ∈ s ′ .c[j] such that m ≻ (s ′ .r j , id j ), thus forcing p j to change to status relaying. This message m was created at a state s 1 (previous to s ′ ) in which s 1 .status i = candidate and m ∈ s 1 .c[(i + 1)]. Between states s 1 and s ′ , process p i must have changed to the relaying status (recall that p j is the last process to change to the relaying status).

In general, every message (r, id n ) with n = x is in a channel c[i] with i ∈ D(x + 1, y) satisfying r < k + 1 and n ∈ D(x + 1, y). These messages were originated at processes at the right of p x , as otherwise they would be in the relaying status by Lemma 1(1). These messages will be discarded by p y upon receiving them.

Recall that at s 2 , (k + 1, id y ) ∈ s 2 .c[y + 1]). The next candidate process p n at the right of p y generates a new message (k + 1, id n ) at some state after s. Therefore, there exists a state s 3 with s 1 → s 3 such that s 3 .status x = candidate, s 3 .r

x = k + 2 and (k + 2, id x ) ∈ s 3 .c[x + 1].
Process p y will have messages (k + 1, id x ) and (k + 2, id x ) in its communication channel c[y] at some state s 5 , where s 5 .r y = k + 1. Message (k + 1, id x ) will be received first (otherwise p y would change to the relaying status). Process p y will only remain as a candidate if id x (-1) k+1 < id y (-1) k+1 . Then, upon receiving (k + 2, id x ) at state s 6 (where s 6 .r y = k + 2 because p y incremented its round number when processing message (k + 1, id x )), process p y will only remain as a candidate if id x (-1) k+2 < id y (-1) k+2 , which is a contradiction with id x (-1) k+1 < id y (-1) k+1 .

✷ Lemma 4

Theorem 2. For every execution, there exists a reachable state s and a process p j such that s.status j = leader.

Proof Every execution starts in an initial state s 0 where at least one process is assumed to be in the candidate status. The execution of successive computation steps will produce new states. As stated in Lemma 4, the number of processes which are in the candidate status decreases as the computation evolves, thus processes change either to the relaying or the leader status until there are no candidates left. According to Theorem 1, if there exists a leader, it must be unique. Moreover, not all candidates can change to the relaying status, as proven in Lemma 2. Consequently, the number of candidates will decrease until eventually only one of them survives. This last candidate will become the leader.

✷ T heorem 2
Remark It is important to notice that (differently from Higham-Przytycka's proof) the previous proof of correctness does not assume that the channels are FIFO. The rest of this section addresses the upper bound issues regarding the number of messages exchanged during the execution of the algorithm depending on whether processes start with the same round number (Theorem 3) or they start with arbitrary round numbers (Theorem 4). Theorem 3. Let us consider an execution in which all processes start with the very same round number. The processes exchange at most O(n log n) messages.

Proof In order to prove that the number of messages is O(n log n) when all the initial round numbers are the same, it is necessary to determine the number of processes needed inside a running cycle of the algorithm so that one of them eventually reaches the greatest round number r g .

Let us consider a running cycle where a given process p 0 has reached the leader status with a round number r g (see Figure 2(a)). According to the proposed algorithm, there are two cases to consider, depending on whether r g is odd or even.

Assume that r g is odd (the same assumptions can be applied to the even case). If p 0 has reached this round number it is due to the fact that there exists another process p 2 with id 0 > id 2 (id 0 < id 2 for the even case), which sent a message that has been received at p 0 , such that r 0 = r 2 = r g -1, as shown in Figure 2(b). Again, if processes p 0 and p 2 reached round r g -1, it was because there exists a third process p 3 such that id 3 > id 0 and id 3 > id 2 (the opposite for the even case). Process p 0 sends a message that is received by p 2 , p 2 sends a message that is received by p 3 and p 3 sends a message that is received by p 0 , where all their associated round numbers are the same, i.e., r 0 = r 2 = r 3 = r g -2 (see Figure 2(c)). If these processes have the same round number at that point, there must be at least another two processes p 1 and p 4 satisfying the same conditions as mentioned before. Hence, we have five processes p 0 , p 1 , p 2 , p 3 , p 4 such that id 3 > id 0 > id 4 > id 2 > id 1 , r 0 = r 1 = r 2 = r 3 = r 4 = r g -3 and the reception of messages is as follows: p 0 receives a message with the same round number as its own but with an identifier id 4 which is lower than id 0 ; p 4 receives a message with the same round number and an identifier id 3 which is greater than id 4 ; p 3 receives a message coming from p 2 such that id 3 is greater than id 2 ; p 2 receives a message from p 1 whose identifier id 1 is lower than id 2 ; and finally, p 1 receives a message from p 0 whose identifier id 0 is greater than id 1 . This new step is depicted in Figure 2(d).

If we continue applying this procedure in an iterative way we will reach a minimum number of processes according to the sequence 1, 2, 3, 5, 8, 13, . . .. This succession of numbers corresponds to the Fibonacci sequence. Without loss of generality, let us assume that the initial round number is 0. Therefore, if a process p i has a round number r i = p, then for every integer q, being q ≤ p, there will exist a set of processes N p-q that will reach a round number pq, given that #N p-q ≥ fib(q + 2). More precisely, there exists a set of processes N 0 that started with an initial status candidate and initial round number r = 0, such that #N 0 ≥ fib(p + 2). This means that if we have x processes whose status at startup time is candidate, we can assert that the number of processes that will reach a round number r = p in the worst case is x ≥ fib(p + 2).

Let us consider a ring with n processes that start at round number 0. Hence, we can delimit the greatest round number L with the value n ≥ fib(L + 2). By means of the Fibonacci expression:

fib(r) = c • (p r -q r ), with p = 1+ √ 5 2 , q = 1- √ 5 2 , c = 1 √ 5 .
(id , r ) We can set an upper bound for L based on the number of processes initially composing the ring (n) by substituting the aforementioned expression in n ≥ fib(L + 2):

n ≥ 1 √ 5 1+ √ 5 2 L+2 -1- √ 5 2 L+2 .
The second term of the difference is upper bounded by the value of L = 2, which gives a value of 0.15:

√ 5 • n + 0.15 ≥ 1+ √ 5 2

L+2

.

Applying logarithms to both sides of the inequality results in the following expression:

log( √ 5 • n + 0.15) ≥ (L + 2) • log 1+ √ 5 2
. Thus, we can define the upper limit of L for a given set of n processes in the following manner:

L ≤ log( √ 5•n+0.15) 0.21 -2.
This result asserts that the maximum round number that a process can reach is O(log n). Since n messages a re necessary for each round, the total number of messages is O(n log n).

✷ T heorem 3

Theorem 4. Let us consider an execution in which all processes start with arbitrary round numbers. The processes exchange at most O(n 2 ) messages.

Proof The worst case initialization is when

Collection des Publications Internes de l'Irisa c IRISA

• We have for 0 ≤ i ≤ n -2: id i < id i+1 and the initial values of the round numbers are such that r i < r i+1 (e.g., id i = r i = i), and

• The orientation of the unidirectional ring is p n-1 , p n-2 , ..., p 1 , p 0 , p n-1 .

In that case, the algorithm behaves exactly as Chang and Robert's unidirectional leader election algorithm [START_REF] Chang | An Improved Algorithm for Decentralized Extrema Finding in Circular Configurations of processes[END_REF] whose message complexity is O(n 2 ).

More precisely, we have the following. All processes are initially candidates and each process p i sends the message (i, id i ). The message (0, id 0 ) sent by p 0 is stopped by p n-1 which discards it. The message (1, id 1 ) sent by p 1 is forwarded by p 0 and then stopped by p n-1 which discards it. Etc. until the message (n -1, id n-1 ) sent by p n-1 is forwarded by p n-2 , p n-3 , ..., p 1 , p 0 which forwards it to p n-1 , which elects itself as a leader. The total number of sent/forwarded messages is consequently 1 + 2 + • • • + (n -1) + n, i.e., O(n 2 ).

Remark. This initialization is the worst because it is the one that favors message forwarding as much as possible. ✷ T heorem 4

Conclusion

This paper has introduced and investigated the notion of leader election with graceful degradation. In the context of leader election algorithms, graceful degradation is related to the initial values of local variables and message complexity. More precisely, a gracefully degrading leader election algorithm has to behave optimally when the local variables have "good" initial values, while it may not behave optimally (while still electing a leader) when local variables have "bad" initial values. Optimal means O(n log n) messages, while non-optimal means O(n 2 ) messages. The paper has presented such a gracefully degrading leader election algorithm. This algorithm, based on a principle introduced by Higham and Przytycka in [START_REF] Higham | A Simple Efficient Algorithm for Maximum Finding on Rings[END_REF], is optimal with respect to the number of messages when the processes start with the same round number while it can require up to O(n 2 ) messages when the processes start with arbitrary round numbers.

Finally, beyond the leader election problem, the study of algorithms whose complexity gracefully degrades according to the initial values of local variables is an approach that seems worth pursuing from both practical and theoretical point of views.

Figure 1 :

 1 Figure 1: Gracefully degrading leader election algorithm (code for p i )

  Set of processes at r = rg. (b) Set of processes at r = rg -1. Set of processes at r = rg -2. (d) Set of processes at r = rg -3.

Figure 2 :

 2 Figure 2: Analysis of the communication cost in the worst case of the proposed leader election algorithm

  : if (status i = candidate) then send (r i , id i ) end if.

	repeat
	(01)	receive (r, id);
	(02)	if (status i = candidate)
	(03)	then case
	(04)	r = r i : case
	(05)

init

Collection des Publications Internes de l'Irisa c IRISA

This argument is now applied to the last state s ′ 1 in which p i was in the candidate status. We have that s 1 → s ′ 1 → s ′ . At s ′ 1 , there exists a message m ′ = (s 2 .r k , id k ), with m ′ ∈ s ′ 1 .c [i] such that m ′ ≻ (s ′ 1 .r i , id i ). This message m ′ was created in a state s 2 (previous to s ′ 1 ) at which s 2 .status k = candidate and m ′ ∈ s 2 .c[(k + 1)].

By Lemma 1 [START_REF] Attiya | Computing on an Anonymous Ring[END_REF] and the fact that round numbers cannot be decreased, the following relation holds:

Every process p k that changes to the relaying status before p j satisfies this order relation in the left direction of the ring with respect to p j , i.e., (s.r k , id k ) ≻ (s.r j , id j ). Therefore, there exists a process, namely p x , such that it is the first process at the right of p j such that it was a candidate at some state after the initial state and changed to the relaying status before state s ′ . Process p j was a candidate from states s 0 to s ′ . By the algorithm code, the channels from p j to p x can only contain messages originated at p j . Let m ′′ = (s 3 .r j , id j ) ∈ s 3 .c[x] be the last message originated at p j , being s 3 the last state in which s 3 .status x = candidate. In order for p j to change to the relaying status, m ′′ ≻ (s 3 .r x , id x ) must hold. Due to Lemma 1(2) and the fact that s 0 → s 3 → s, it is true that (s.r j , id j ) m ′′ ≻ (s.r x , id x ).

However, recall that we have shown before that for every process p k that changes to the relaying status before p j it holds that (s.r k , id k ) ≻ (s.r j , id j ). Thus, for p x we have that (s.r x , id x ) ≻ (s.r j , id j ), which contradicts (s.r j , id j )

After showing that not all processes can be in the relaying status, we must prove that the number of candidate processes decreases as the computation evolves until one of them is elected as the leader. This statement is formalized in Lemma 4, which uses Lemma 3 to ensure that there always exists a message with the current maximum round number of the ring. Lemma 3. Let s be a reachable state of any execution achieved after executing step init i for any i ∈ I such that s.status i = candidate and s.r i = k being k the current maximum round number in the ring (i.e., ∀j ∈ I, s.r j ≤ k). Then, there exist j, l ∈ I such that

Proof By contradiction, let us assume that ∀j, l ∈ I : (k, id j ) / ∈ s.c [l]. By the algorithm code, there must exist a reachable state s 1 → s at which p i sent a message containing its round number and identifier; i.e., s 1 .status i = candidate, s 1 .r i = k, and (k,

The disappearance of message (k, id i ) must have been due to a computation step executed by some process p j at a reachable state s 2 that results in another state s 3 , where

, s 1 → s 2 → s 3 and either s 3 → s or s 3 = s. This is possible if and only if s 2 .status j = candidate, j = i and s 2 .r j = k. Note that: (a) if j = i then s 3 .status i = leader and hence s.status i = candidate; (b) if s 2 .r j > k then k is not the maximum round number at s; and (c) if s 2 .r j < k then (k, id i ) ∈ s 3 .c[j + 1] and s 3 .status j = s.status j = relaying. Therefore, if s 2 .r j = k and id j (-1) k > id i (-1) k , then s 3 .r j = k + 1, thus k cannot be the maximum round number in the ring at s. On the other hand, if s 2 .r j = k and id j (-1) k < id i (-1) k , then s 3 .status = s.status = relaying.

Let s ′ be the state previous to s 2 at which p j sent the message containing its current round number and identifier; i.e., s ′ .status j = candidate and (k, id j ) ∈ s ′ .c[j + 1]. By the initial assumption, (k, id j ) / ∈ s.c[l] for all l ∈ I. By replacing i by j and j by n in the previous argumentation, we conclude that all processes in the ring are in the relaying status, which is a contradiction with Lemma 2.

✷ Lemma 3

In the following, #candidates(s) represents the number of candidate processes in a state s, i.e., #candidates(s) = |{i ∈ I : s.status i = candidate}|. Lemma 4. For every reachable state s of any execution, there exits a reachable state s ′ such that s → s ′ and #candidates(s) > #candidates(s ′ ) or ∃j ∈ I : s ′ .status j = leader.

Proof By contradiction, let us assume a reachable state s ′ , s → s ′ , where ∀j ∈ I : s ′ .status j = leader and #candidates(s) ≤ #candidates(s ′ ).

The algorithm never increments the number of initial candidate processes, i.e., none of the processes p j such that s.status j = relaying can become a candidate after s happens. Thus, ∀s ′ : s → s ′ : #candidates(s) = candidates(s ′ ).

By Lemma 2, #candidates(s) > 0. Being k be the maximum round number at s, by Lemma 3 there exists a message (k, id j ) ∈ s.c[l] for some j, l ∈ I.

Let p x be the first process at the right of p l-1 such that s.status x = candidate (note that x may be l). Since (k, id j ) will eventually be received by p x (which will still be a candidate after processing the message), there exists a first state s 1 such that s 1 .status x = candidate, s 1 .r x = k + 1 and (k + 1, id x ) ∈ s 1 .c[x + 1], with s → s 1 . Note that if x = j, then by Lemma 1(1), ∀i ∈ D(x, x) : s.status i = relaying. Therefore, either (k, id x ) changes p x to the leader status or another message (k ′ , id x ) with k ′ ≥ k will eventually change p x to the leader status after traveling around the ring. These two cases are a contradiction with the initial assumption, thus x = j.

Let p y be the first process at the right of p x such that s.status y = candidate. Processes p x and p y cannot be the same, because (k + 1, id x ) ∈ s 1 .c[x + 1] and ∀i ∈ D(x, x) : s.status i = relaying, which would make p x the leader. Hence, we have that x = y and (k + 1, id x ) ∈ s 1 .c[x + 1]. This implies that there must be a first state s 2 such that s 2 .status y = candidate, s 2 .r y = k + 1 and (k + 1, id y ) ∈ s 2 .c[y + 1]. This is possible because s.r y ≤ k.


Luc Boruta
email: luc.boruta@inria.fr

Combining Indicators of Allophony

Allophonic rules are responsible for the great variety in phoneme realizations. Infants can not reliably infer abstract word representations without knowledge of their native allophonic grammar. We explore the hypothesis that some properties of infants' input, referred to as indicators, are correlated with allophony. First, we provide an extensive evaluation of individual indicators that rely on distributional or lexical information. Then, we present a first evaluation of the combination of indicators of different types, considering both logical and numerical combinations schemes. Though distributional and lexical indicators are not redundant, straightforward combinations do not outperform individual indicators.

Introduction

Though the phonemic inventory of a language is typically small, phonetic and phonological processes yield manifold variants1 for each phoneme. Words too are affected by this variability, yielding different realizations for a given underlying form. Allophonic rules relate phonemes to their variants, expressing the contexts in which the latter occur. We are interested in describing procedures by which infants, learning their native allophonic grammar, could reduce the variation and recover words. Combining insights from both computational and behavioral studies, we endorse the hypothesis that infants are good distributional learners [START_REF] Maye | Infant sensitivity to distributional information can affect phonetic discrimination[END_REF][START_REF] Saffran | Statistical learning by 8-month-old infants[END_REF] and that they may 'bootstrap' into language tracking statistical regularities in the signal.

We seek to identify which features of infants' input are most reliable for learning allophonic rules. A few indicators, based on distributional [START_REF] Peperkamp | The acquisition of allophonic rules: statistical learning with linguistic constraints[END_REF] and lexical (Martin et al., submitted) information, have been described and validated in silico. 2 Yet, other aspects have barely been addressed, e.g. the question of whether or not these indicators capture different aspects of allophony and, if so, which combination scheme yields better results.

We present an extensive evaluation of individual indicators and, based on theoretical and empirical desiderata, we outline a more comprehensive framework to model the acquisition of allophonic rules.

Indicators of allophony

We build upon Peperkamp et al.'s framework: the task is to induce a two-class classifier deciding, for every possible pair of segments, whether or not they realize the same phoneme. Discrimination relies on indicators, i.e. linguistic properties which are correlated with allophony. As a model of language acquisition, this classifier is induced without supervision.

In line with previous studies, we assume that infants are able to segment the continuous stream of acoustic input into a sequence of discrete segments, and that they quantize each of these segments into one of a finite number of phonetic categories. Quantization is a necessary assumption for the framework to apply. However, the larger the set of phonetic categories, the closer we get to recent 'single-stage' approaches (e.g. work by Dillon et al., in preparation) where phonological categories are acquired directly from raw infant-directed speech.

Distributional indicators

Complementary distribution is a ubiquitous criterion for the discovery of phonemes. If two segments occur in mutually exclusive contexts, the two may be realizations of the same phoneme.

Bearing in mind that the signal may be noisy, [START_REF] Peperkamp | The acquisition of allophonic rules: statistical learning with linguistic constraints[END_REF] looked for segments in near-complementary distributions. Using the symmetrised Kullback-Leibler divergence (henceforth KL), they compared the probability distributions of how often the contexts of each segment occur. In a follow-up study, Le Calvez (2007) compared KL to other indicators, namely the Jensen-Shannon divergence (JS) and the Bhattacharyya coefficient (BC).3

Lexical indicators

Adjacent segments can condition the realization of a word's initial and final phonemes. If two words only differ by their initial or final segments, these segments may be realizations of the same phoneme. Instantiating the general concept of functional load [START_REF] Hockett | A manual of phonology[END_REF], lexical indicators gauge the degree of contrast in the lexicon between two segments.

Using the simplest expression of functional load, Martin et al. (submitted) defined a Boolean-valued indicator, FL, satisfied by a single pair of minimally different words. As a result, FL is sensitive to noise. We define a finer-grained variant, FL*, which tallies the number of such pairs. Moreover, as words get longer, it becomes increasingly unlikely that such word pairs occur by chance. Thus, for any such pair, FL* is incremented by the length of those words.

We also propose an information-theoretic lexical indicator, HFL, based on Hockett's definition of functional load. HFL accounts for the fraction of information content, represented by the language's word entropy, that is lost when the opposition between two segments is neutralized. The 'broken typewriter' function used for neutralization guarantees that values lie in [0, 1] ( [START_REF] Anthony | Theory of Neural Information Processing Systems[END_REF].

Corpora and experimental setup

In the absence of phonetic transcriptions of infantdirected speech, and as the number of allophones in-fants must learn is unknown (if assessable at all), we use Boruta et al.'s (submitted) corpora. They created a range of possible inputs, applying artificial allophonic grammars4 of different sizes [START_REF] Boruta | A note on the generation of allophonic rules[END_REF] to the now-standard CHILDES 'Brent/Ratner' corpus of English [START_REF] Brent | Distributional regularity and phonotactic constraints are useful for segmentation[END_REF]. We quantify the amount of variation in a corpus by its allophonic complexity, i.e. the ratio of the number of phones to the number of phonemes in the language.

Lexical indicators require an ancillary procedure yielding a lexicon. Martin et al. approximated a lexicon by a list of frequent n-grams. Here, the lexicon is induced from the output of an explicit word segmentation model, viz. Venkataraman's incremental (2001) model, using the unsegmented phonetic corpora as the input. Though, obviously, infants can not access it, we use the lexicon derived from the CHILDES orthographic transcripts for reference.

Indicators' discriminant power

As the aforementioned indicators have been evaluated using various languages, allophonic grammars and measures, we present a unified evaluation, conducted using Sing et al.'s (2005) ROCR package.

Evaluation

Non-Boolean indicators require a threshold at and above which pairs are classified as allophonic. We evaluate indicators across all possible discrimination thresholds, reporting the area under the ROC curve (henceforth AUC). Equivalent to Martin et al.'s ρ, values lie in [0, 1] and are equal to the probability that a randomly drawn allophonic pair will score higher than a randomly drawn non-allophonic pair;

.5 thus indicates random prediction.

Moreover, we evaluate indicators' misclassifications at the discrimination threshold maximizing Matthews' (1975) correlation coefficient: let α, β, γ and δ be, respectively, the number of false positives, false negatives, true positives and true negatives, MCC = (γδ -αβ)/ (α+γ)(β +γ)(α+δ)(β +δ).

Values of 1, 0 and -1 indicate perfect, random and inverse prediction, respectively. This coefficient is more appropriate than the accuracy or the F-measure when, as here, the true classes have very different sizes. 5 Using this optimal, MCC-maximizing threshold, we report the maximal MCC and, as percentages, the accuracy (Acc), the false positive rate (FPR) and the false negative rate (FNR).

Results and discussion

Indicators' AUC corroborate previous results for distributional indicators: they perform almost identically and do not accommodate high allophonic complexities at which they perform below chance (Figure 1.a) because, as suggested by Martin et al., every segment has an extremely narrow distribution and complementary distribution is the rule rather than the exception. By contrast, all three lexical indicators are much more robust even if, as predicted, FL's coarseness impedes its discriminant power (Figure 1.b). 6 The reason why FL* outperforms HFL may be due to the very definition of HFL's broken typewriter function: as the segments, e.g. {x, y}, are collapsed into a single symbol, the indicator captures not only minimal alternations like wx ∼ wy, but also word pairs such as xy ∼ yx.

AUC curves suggest that, for each type, indicators converge at medium allophonic complexity. Thus, misclassification scores are reported in Table 1 only at low (2 allophones/phoneme) and medium (9) complexities. Previous observations are confirmed by MCC and accuracy values: though all indicators are positively correlated with the underlying allophonic relation, correlation is stronger for lexical indicators. Surprisingly, zero FPR values are observed for some lexical indicators, meaning that they make no false alarms and, as a consequence, that all errors are caused by missed allophonic pairs.

Indicators' redundancy

None of the indicators we benchmarked in the previous section makes a perfect discrimination between allophonic and non-allophonic pairs of segments.

5 If p phonemes have on average a allophones, out of the pa(pa -1)/2 possible pairs, only pa(a -1)/2 are allophonic, and a dummy indicator that rejects all pairs achieves a constant accuracy of 1 -(a -1)/(pa -1), which is greater than 98% for any of our corpora. Besides, the computation of precision, recall and the F-measure do not take true negatives into account.

6 These indicators perform similarly using the orthographic lexicon: we only report AUC for FL* (referred to as oFL*), as it gives the upper bound on lexical indicators' performance. 0 5 10 15 20 25 0.4 0.5 0.6 0.7 0.8 0.9 a. Distributional

• • • • • • • • KL JS BC
0 5 10 15 20 25 0.4 0.5 0.6 0.7 0.8 0.9 b. Lexical Yet, if some segment pairs are misclassified by one but not all (types of) indicators, a suitable combination should outperform individual indicators. In other words, combining indicators may yield better results only if, individually, indicators capture different subsets of the underlying allophonic relation.

Evaluation

To get a straightforward estimation of redundancy, we compute the Jaccard index between each indicator's set of misclassified pairs: let D and L be sets containing, respectively, a distributional and a lexical indicator's errors, J(D, L) = |D ∩ L|/|D ∪ L|. Values lie in [0, 1] and the lower the index, the more promising the combination. To distinguish false positives from false negatives, we compute two Jaccard indices for each possible combination.

Results and discussion

Jaccard indices, reported in Table 2, emphasize the distinction between false positives and false negatives. False negatives have rather high indices: most allophonic pairs that are not captured by distributional indicators are not captured either by lexical indicators, and vice versa. By contrast, there is little or no redundancy in false positives, even at medium allophonic complexity: though random pairs can be incorrectly classified as allophonic, the error is unlikely to recur across all types of indicators.

It is also worth noting that though JS performs slightly better than KL and BC, the exact nature of the distributional indicator seems to have little influence on the performance of the combination.

Combining indicators

As distributional and lexical indicators are not completely redundant, combining them is a natural extension. However, not all conceivable combination schemes are appropriate for our task. We present our choices in terms of [START_REF] Marr | Vision: a Computational Investigation into the Human Representation and Processing of Visual Information[END_REF] levels of analysis.

At the computational level, a combination scheme can be either disjunctive or conjunctive, i.e. each indicator can be either sufficient or (only) necessary. Aforementioned indicators were designed as necessary but not sufficient correlates of phonemehood. For instance, while a phoneme's allophones have complementary distributions, not all segments that have complementary distributions are allophones of a single phoneme. Therefore, we favor a conjunctive scheme,7 even if this conflicts with abovementioned results: most errors are due to missed allophonic pairs but a conjunctive scheme, where every indicator must be satisfied, is likely to increase misses.

At the algorithmic level, a combination scheme can be either logical or numerical. A logical scheme uses a logical connective to join indicators' Boolean decisions, typically by conjunction according to our previous decision. By contrast, a numerical scheme tries to approximate interactions between indicators' values, merging them using any monotone increasing function; discrimination then relies on a single threshold. In practical terms, we use multiplication as a numerical counterpart of conjunction.

Evaluation

Setting aside the following minor adjustments, we use the same protocol as for individual indicators. 0 5 10 15 20 25 0.4 0.5 0.6 0.7 0.8 0.9 Logical combinations require one discrimination threshold per combined indicator. As it facilitates comparison with previous results, we report performance at the thresholds maximizing the MCC of individual indicators (rather than at the thresholds maximizing the combined MCC) .

• • • • • • • • JS . FL JS . FL* JS . HFL JS . oFL*
Numerical combinations are sensitive to differences in indicators' magnitudes. Equal contribution of all indicators may or may not be a desirable property, but in the absence of a priori knowledge of indicators' relative weights, each indicator's values were standardized so that they lie in [0, 1], shifting the minimum to zero and rescaling by the range.

Results and discussion

It is worth noting that, while the performance of combined indicators is still good ( show that conjoined and multiplied indicators perform similarly, disparities emerge at medium allophonic complexity: while multiplication yields better MCC and FNR, conjunction yields better accuracy and FPR. In that regard, observing FPR values of zero is quite satisfactory from the point of view of language acquisition, as processing two segments as realizations of a single phoneme (while they are not) may lead to the confusion of true minimal pairs of words. Indeed, at a higher level, learning allophonic rules allows the infant to reduce the size of its emerging lexicon, factoring out allophonic realizations for each underlying word form. Furthermore, AUC curves for the multiplicative scheme (Figure 2),8 most notably FL's, suggest that distributional indicators' contribution to the combinations appears to be rather negative, except at very low allophonic complexities. One explanation (yet to be tested experimentally) would be that they come into play later in the learning process, once part of allophony has been reduced using other indicators.

Conclusion

We presented an evaluation of distributional and lexical indicators of allophony. Although they all perform well at low allophonic complexities, misclassifications increase, more or less seriously, when the average number of allophones per phoneme increases. We also presented a first evaluation of the combination of indicators, and found no significant difference between the two combination schemes we defined. Unfortunately, none of the combinations we tested outperforms individual indicators.

For comparability with previous studies, we only considered combination schemes requiring no modification in the definition of the task; however, learning allophonic pairs becomes unnatural when phonemes can have more than two realizations. Embedding each indicator's segment-to-segment (dis)similarities in a multidimensional space, for example, would enable the use of clustering techniques where minimally distant points would be analyzed as allophones of a single phoneme.

Thus far, segments have been nothing but abstract symbols and, for example, the task at hand is as hard for [a] ∼ [a ˚] as it is for [4] ∼ [k]. However, not only do allophones of a given phoneme tend to be acoustically similar, but acoustic differences may be more salient and/or available earlier to the infant than complementary distributions or minimally differing words. Therefore, the main extension towards a comprehensive model of the acquisition of allophonic rules would be to include acoustic indicators.

Figure 2 :

 2 Figure 2: Indicators' AUC as a function of allophonic complexity, for the multiplicative combination scheme. The dashed line indicates random prediction.

Table 1 :

 1 Indicators' performance at low and medium complexities, using the MCC-maximizing thresholds. Boldface indicates the best value. Italics indicate accuracies below that of a dummy indicator rejecting all pairs.

	• •	•	•	•	•	•
				•	FL FL* HFL oFL*

Table 2 :

 2 Indicators' redundancy at low and medium allophonic complexities, estimated by the Jaccard indices between their false positives (FP) and false negatives (FN). Boldface indicates the best value.

	2 allo./phon. 9 allo./phon.
	FP	FN	FP	FN
	KL FL .096 .071 .113 .359
	JS FL .113 .076 .071 .355
	BC FL .110 .075 .118 .358
	KL FL* .000 .595 .008 .520
	JS FL* .000 .548 .005 .525
	BC FL* .000 .556 .007 .517
	KL HFL .000 .667 .087 .788
	JS HFL .000 .612 .033 .781
	BC HFL .000 .620 .089 .787

Table 3 )

 3 , it is less satisfactory than that of the best individual indicators. Moreover, even if misclassification scores

		Logical combination: conjunction	Numerical combination: multiplication
		2 allophones/phoneme 9 allophones/phoneme 2 allophones/phoneme 9 allophones/phoneme
		MCC Acc FPR FNR MCC Acc FPR FNR MCC Acc FPR FNR MCC Acc FPR FNR
	KL FL	.104 92.9 06.5 67.3 .037 94.7 03.6 91.3 .104 92.9 06.5 67.3 .116 73.1 26.7 35.2
	JS FL	.109 91.7 07.8 62.6 .032 96.2 02.1 94.6 .110 91.5 07.9 61.9 .116 73.1 26.7 35.2
	BC FL	.109 91.9 07.5 63.3 .038 94.5 03.9 90.8 .109 92.8 06.6 66.0 .116 73.1 26.7 35.2
	KL FL* .457 99.2 00.0 78.9 .207 98.2 00.1 93.3 .526 99.3 00.0 71.4 .371 98.4 00.1 81.6
	JS FL* .465 99.2 00.0 78.2 .153 98.2 00.0 95.7 .548 99.3 00.0 66.0 .393 98.4 00.2 78.3
	BC FL* .465 99.2 00.0 78.2 .211 98.2 00.1 93.0 .535 99.3 00.0 68.7 .388 98.4 00.1 79.0
	KL HFL .348 99.1 00.0 87.8 .078 97.0 01.3 93.5 .363 99.1 00.0 84.4 .117 90.3 08.4 73.7
	JS HFL .348 99.1 00.0 87.8 .068 97.9 00.3 96.5 .359 99.1 00.1 83.7 .119 90.4 08.4 73.9
	BC HFL .348 99.1 00.0 87.8 .077 96.9 01.4 93.2 .361 99.1 00.0 85.7 .119 90.3 08.4 73.5

Table 3 :

 3 Performance of combined distributional and lexical indicators, at low and medium allophonic complexity. Boldface indicates the best value. Italics indicate accuracies below that of a dummy indicator rejecting all pairs.

We use allophony as an umbrella term for the continuum ranging from typical allophones to mere coarticulatory variants.

See also the work of[START_REF] Dautriche | Modélisation des processus d'acquisition du langage par des méthodes statistiques[END_REF] on acoustic indicators of allophony, albeit using adult-directed speech.

As for the actual computations, we use the same definitions as Le Calvez (2007) except that, as BC increases when distributions overlap and 0 ≤ BC ≤ 1, we actually use 1-BC.

Because all allophonic rules implemented in the corpora are of the type p → a / c, FL and FL* only look for words minimally differing by their last segments.

This generalizes Martin et al.'s attempt at combination: they used FL as a high-pass lexical filter prior to the use of KL.

We do not report a threshold-free evaluation for the logical scheme. As it requires the estimation of the volume under a surface, comparison between schemes becomes difficult. Moreover, as the exact definition of the distributional indicator does not affect the results, we only plot combinations with JS.

Acknowledgments

This work was supported by a graduate fellowship from the French Ministery of Research. We thank Benoît Crabbé, Emmanuel Dupoux and Sharon Peperkamp for helpful comments and discussion.