Michel Minoux

Vincent Mousseau

Solution Repair/Recovery in Uncertain Optimization Environment

Introduction

Operation Research deals with the application of advanced analytical methods such as optimization models applied to help in taking better decisions. Theoretically, models are developed, tested and then operated in an organization. Unfortunately, the environment wherein the solution is developed differs from the one wherein the solution is operated. Different unexpected events occur while operating the optimal decision, therefore there is a need expressed by the operators which is the ability to quickly adapt a plan in operation to take into account events making it anymore or in part inapplicable.

During the last few years, Optimization Solution Team within IBM has been involved in the development of optimization solutions for planning and scheduling for industrial markets with strong potential. To better match the needs of their customers, they seek to develop methods and software tools for repair or recovery.

The current research project is intended as a contribution to equip the existing optimization models of IBM (mainly Mixed-Integer Programming, Linear Programming or Constraint Programming) with repair capabilities in order to propose optimization solutions which can be operated as widely as possible.

Context

Operation management problems (such as Production Planning and Scheduling) are represented and formulated as optimization models. The resolution of such optimization models leads to solutions which have to be operated in an organization. However, the conditions under which the optimal solution is obtained rarely correspond exactly to the conditions under which the solution will be operated in the organization.

Therefore, in most practical contexts, the computed optimal solution is not anymore optimal under the conditions in which it is operated. Indeed, it can be "far from optimal" or even not feasible. For different reasons, we hadn't the possibility to completely re-optimize the existing solution or plan. As a consequence, it is necessary to look for "repair solutions", i.e., solutions that have a good behavior with respect to possible scenarios, or with respect to uncertainty of the parameters of the model. To tackle the problem, the computed solution should be such that it is possible to "repair" it through a local re-optimization guided by the user or through a limited change aiming at minimizing the impact of taking into consideration the scenarios.

Goals

As announced in the introduction, the operational purpose of this research project is the development of repair/recovery infrastructures which will be added to the existing solutions developed by IBM. In view of achieving this goal, we propose to carry out some preparatory research work concerning the optimization of two problems related to production planning and scheduling.

The first step in this investigation will be to advance the state of the art in the models and algorithms used to formulate and solve the problems. It tries to optimize problems related to production planning and to scheduling in order to propose mathematical formulations for the existing solutions. Therefore, we will have the possibility to compare them with models already proposed in the literature and to evaluate to what extent the solutions proposed existing approaches are different.

After modeling the existing solutions and validating them using Cplex and OPL, the next objective of this research will be to calculate a repair solution given:

 A current plan with a common set of decision variables  A number of scenarios grouping a set of frozen variables and relaxable constraints  A new objective function composed of a combination of a set of Key Performance Indicator (KPI) presenting the impact of taking into consideration scenarios and the initial solution.

The repair solutions will be built on existing functionalities developed by IBM such as Complex Project Scheduling (CPS) and Production Planning and Scheduling (PPS). It will be conducted in relation with the development of infrastructure configuration solutions, allowing business experts to configure 'repairable' solutions.

Research Organization

We will start by investigating robust optimal solution and concepts for solution repair. We will deal with two study cases belonging to the family of CPS and PPS and try in an early stage to extend these solutions and concepts to more general optimization problems.

These study cases are developed in a platform called IBM ILOG ODME (Operational Decision Management Enterprise). ODME is a platform to implement and deploy corporate custom solutions for optimization-based planning and scheduling. Developing a realistic plan or schedule provides the best possible balance between customer service and revenue goals.

With ILOG ODM Enterprise, business leaders can make better decisions through what-if analysis, scenario management, and collaboration.

Tail Assignment

The first study case is a solution developed by IBM in the context of airline operations called Tail Assignment which is the problem of creating routes for a set of individual aircraft, covering a set of flights in a timetable so that various operational constraints are satisfied while minimizing some cost functions.

Tail Assignment or Aircraft routing is a part of the sequential procedure used by airlines to plan their operations. They first start by modeling the market behavior to construct a timetable containing information about the time and place of the arrival and departure of each flight. Then, the fleet assignment is performed to assign an aircraft type to each flight leg to maximize anticipated profit while taking into account the number of available aircraft. For each aircraft type, an aircraft routing problem is then solved by determining the sequence of flight legs to be flown by each individual aircraft.

Before investigating the issue of repair, we will start formulating Tail assignment as a MIP mathematical model [START_REF] Minoux | Programmation Mathematique. Theorie et Algorithmes[END_REF]]. The model consists as described above of assigning an aircraft to a flight while respecting the main constraints below:

C1 : Minimum allowed time between the arrival and departure of an aircraft, needed for activities of cleaning, refueling, changing crew and passengers….

C2 : Planes must depart from an initial position, that means the first flight operated by an aircraft must have as a departure airport the initial position of the aircraft C3 : Flights are with no ferry represent a flight without passengers or even commercial flights. For one aircraft, the arrival airport for a flight should be the same as the departure flight operated by the same aircraft.

Generally, modeling and solving aircraft routing problem are well studied in the literature [START_REF] Liang | The Aircraft Maintenance Routing Problem[END_REF]] and recently in regard to the occurrence of disruptions such as flight delays, cancellation... there has been a focus on introducing robustness into airline planning phases to mitigate the effect of these disruptions.

Normally strict robustness [START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Tal | Robust Optimization, methodology and applications[END_REF] requires a planned solution to perform under all disruptions, but what we need is to recognize that in a disruption, repair also called in literature 'recovery' is required and the planned solution will be changed in operations. The contrast between robust and repair is well explained in the article of [START_REF] Liebchen | The concept of recoverable robustness, linear programming recovery, and railway applications[END_REF]].

To summarize, we will develop a two stage Tail assignment model composed by a planning stage and a recovery stage based on specific scenarios proposed by IBM such as Flight delay, cancellation, and last time aircraft unavailability [START_REF] Minoux | On 2-Stage Robust Optimization with RHS uncertainty, complexity results and applications[END_REF]]... The two stages are solved either simultaneously or separately to improve the robustness of the planned solution.

Production Planning

The second study case is a classical production planning problem [START_REF] Murla | Models for production planning under uncertainty : A review[END_REF]]. The objective of this application is to decide how much of which product must be produced at each location for a given time period.

The planning can also include the decisions on the transportation of raw materials between suppliers and production locations, transportation of intermediate products between different production locations, and transportation of finished products between production location and customers.

Objectives may include minimization of production, inventory and transportation cost along with minimization of penalties related to target inventories, or target demand and/or forecast to cover.

We will adapt the same methodology as for the first study case; starting from mathematical modeling of the problem until generating algorithm of repair based on specific scenarios. Some typical repair scenarios in this context are the following:

Scenario 1. A constraint requires that all customers of priority must have all their orders being fulfilled. The optimization engine is run and finds feasible and optimal solutions. The business user modifies the priority of a given customer to be greater than the threshold. This is an infeasibility that needs to be detected and repaired, without re-running the complete optimization algorithm that can take minutes or hours to run.

Scenario 2. A new order is created after optimization is run so that the plan does not include the decision to produce and transport products to fulfill this order. We want to detect and repair this.

Generalization

Dealing with two study cases with different models of repair helps us to study the similarity between them in order to propose a more general framework of repair which could be coupled with that of any model of mathematical programming offering to the users a better apprehension of the solutions. The general framework leans on a specific definition of scenarios, related criteria in order to define the impact of taking into consideration scenarios on the initial solution and finally repair algorithms. To model repair algorithms, a possible idea would be e.g. to explore possible connections with VNS (Variable Neighborhood Search) [START_REF] Hansen | Variable neighbourhood search: methods and applications[END_REF]. The reason for this is that VNS is also based on repeatedly solving local reoptimization sub problems.

After modeling general algorithm of repair, we will focus on studying robustness issues and try to setup new criteria of robustness which are based on repair. Relating robustness and recovery is a fairly new research subject aiming at defining robust solutions with a minimum possible effort [START_REF] Froyland | The recoverable robust tail assignment problem[END_REF]]. We will explore this issue in our research in order to highlight the relationship between a robust solution and reparable solution and see how far we can conclude that reparability is a quality of robust solution that contributes to define new criteria of robustness. So we can assume that the final deliverable of our project is the elaboration of a recoverable robustness framework leading to solutions that can be repaired with limited changes.

Another subject that will be considered in our research is the relationship with the decisionmaker about the criteria, the scenario set and the definition of robustness [START_REF] Thengvall | Balancing user preferences for aircraft schedule recovery during irregular operations[END_REF]. There is a parallel relation with Multi Criteria Decision Making [START_REF] Bouyssou | Evaluation and Decision Models with Multiple Criteria : Stepping stones for the analyst Series[END_REF]] based on introducing the preference of the user. It goes toward decision aid systems leading to some degree of robustness [START_REF] Greco | Ordinal regression revisited: Multiple criteria ranking using a set of additive value functions[END_REF]].

To validate the general framework, we will test it in connection with other application examples provided by IBM in order to specify further integration framework in the existing optimization tools developed by IBM.

Another interesting issue that can lead to further developments of the proposed research concerns the extension of the repair algorithms to Constraint Programming models. Even if it impossible, in the present stage, to anticipate how far it will be possible to go in this direction, attempts will be made to properly identify those concepts resulting from the work which are likely to be applicable to the Constraint Programming field.

To have clearer vision of how our work will be organized, we propose the following Gantt chart of activities:

('To' denotes the starting date of the PhD)

Figure 1 :

 1 Figure 1 : PhD organization


come

An experimental assessment of the "Gibbs-Energy and Empirical-Variance" estimating equations (via Kalman smoothing) for Matérn processes

Didier A.


Mireille Bousquet-M Élou

DISCRETE EXCURSIONS

It is well-known that the length generating function E(t) of Dyck paths (excursions with steps ±1) satisfies 1 -E + t 2 E 2 = 0. The generating function

, where the F k are polynomials in t given by

. This means that the generating function of these polynomials is k≥0 F k z k = 1/(1 -z + t 2 z 2 ). We note that the denominator of this fraction is the minimal polynomial of the algebraic series E(t).

This pattern persists for walks with more general steps. For any finite set of steps S, the generating function E (k) (t) of excursions (generalized Dyck paths) taking their steps in S and of height at most k is the ratio F k /F k+1 of two polynomials. These polynomials satisfy a linear recurrence relation with coefficients in Q[t]. Their (rational) generating function can be written k≥0 F k z k = N (t, z)/D(t, z). The excursion generating function E(t) is algebraic and satisfies D(t, E(t)) = 0 (while N (t, E(t)) = 0).

If max S = a and min S = b, the polynomials D(t, z) and N (t, z) can be taken to be respectively of degree d a,b = a+b a and d a,b -a -b in z. These degrees are in general optimal: for instance, when S = {a, -b} with a and b coprime, D(t, z) is irreducible, and is thus the minimal polynomial of the excursion generating function E(t).

The proofs of these results involve a slightly unusual mixture of combinatorial and algebraic tools, among which the kernel method (which solves certain functional equations), symmetric functions, and a pinch of Galois theory.

Introduction

One of the most classical combinatorial incarnation of the famous Catalan numbers, C n = 2n n /(n + 1), is the set of Dyck paths. These are one-dimensional walks that start and end at 0, take steps ±1, and always remain at a non-negative level (Figure 1, left). By factoring such walks at their first return to 0, one easily proves that their length generating function E ≡ E(t) is algebraic, and satisfies

E = 1 + t 2 E 2 .
This immediately yields:

E = 1 - √ 1 -4t 2 2t 2 = n≥0 C n t 2n .
The same factorization gives a recurrence relation that defines the series E (k) ≡ E (k) (t) counting Dyck paths of height at most k:

E (0) = 1 and for k ≥ 1, E (k) = 1 + t 2 E (k-1) E (k) .
This recursion can be used to prove that E (k) is rational, and more precisely, that

E (k) = F k F k+1
, where F 0 = F 1 = 1 and

F k+1 = F k -t 2 F k-1 .
The aim of this paper is to describe what happens for generalized Dyck paths (also known as excursions) taking their steps in an arbitrary finite set S ⊂ Z (see an example in Figure 1, right). Their length generating function E is known to be algebraic. What is the degree of this series? How can one compute its minimal polynomial? Furthermore, it is easy to see that the generating function E (k) can still be written F k /F k+1 , for some polynomials F k . Does the

a i F k-i = 0 (1)
with a i ∈ Q[t], gives a non-linear recursion of order d for the series E (k) ,

d i=0 a i E (k-i+1) • • • E (k) = 0, (2)
and, by taking the limit k → ∞, an algebraic equation of degree d satisfied by E = lim k E (k) :

d i=0 a i E i = 0.
This establishes a close link between the (still hypothetical) recursion for the sequence F k and the algebraicity of E. The connection between (1) and ( 2) is central in the recent paper [START_REF] Ayyer | The number of [old-time] basketball games with final score n : n where the home team was never losing but also never ahead by more than w points[END_REF] dealing with excursions with steps ±1, ±2.

A slightly surprising outcome of this paper is that symmetric functions are closely related to the enumeration of excursions. This can be seen in the following summary of our answers to the above questions. Assume min S = -b and max S = a. Then the excursion generating function E is algebraic of degree at most d a,b := a+b a . The degree is exactly d a,b in the generic case (to be defined), but also when S = {-b, a} with a and b coprime. Computing a polynomial of degree d a,b that cancels E boils down to computing the elementary plethysms e k [e a ] on an alphabet with a + b letters, for 0 ≤ k ≤ d a,b .

The generating function E (k) counting excursions of height at most k is rational and can be written F k /F k+1 for some polynomials F k . These polynomials satisfy a linear recurrence relation of the form (1), of order d a,b , which is valid for k > d a,b -a -b. Moreover, F k can be expressed as a determinant of varying size k, but also as a rectangular Schur function taking the form of a determinant of constant size a + b.

These results are detailed in the next section. Not all of them are new. The generating function of excursions, given in Proposition 1, first appeared in [START_REF] Bousquet-Mélou | Linear recurrences with constant coefficients: the multivariate case[END_REF], but can be derived from the earlier paper [START_REF] Gessel | A factorization for formal Laurent series and lattice path enumeration[END_REF]. An algorithm for computing a polynomial of degree d a,b that cancels E was described in [START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF]. Hence the first part of the next section, which deals with unbounded excursions, is mostly a survey (the results on the exact degree of E are however new). The second partexcursions of bounded height -is new, although an attempt of the same vein appears in [START_REF] Banderier | Combinatoire analytique des chemins et des cartes[END_REF].

Let us finish with the plan of this paper. The kernel method has become a standard tool to solve certain functional equations arising in various combinatorial problems [START_REF] Banderier | Generating functions for generating trees[END_REF][START_REF] De Mier | A solution to the tennis ball problem[END_REF][START_REF] Prodinger | The kernel method: a collection of examples[END_REF]. We illustrate it in Section 3 by counting unbounded excursions. We use it again in Section 4 to obtain the generating function of excursions of bounded height. Remarkably, the same result can be obtained by combining the transfer matrix method and the dual Jacobi-Trudi identity. In Section 5, we determine the recurrence relation satisfied by the polynomials F k . More precisely, we compute the rational series k F k z k . This is equivalent to computing the generating function of rectangular Schur functions k s k a z k , where a = max S. Finally, we discuss in Section 6 the exact degree of the series E for certain step sets S. This involves a bit of Galois theory.

Statement of the results

We consider one-dimensional walks that start from 0, take their steps in a finite set S ⊂ Z, and always remain at a non-negative level. More formally, a (non-negative) walk of length n will be a sequence (s 1 , s 2 , . . . , s n ) ∈ S n such that for all i ≤ n, the partial sum

s 1 + • • • + s i is non-negative. The final level of this walk is s 1 + • • • + s n , and its height is max i s 1 + • • • + s i .
An excursion is a non-negative walk ending at level 0 (Figure 1). We are interested in the enumeration of excursions.

The generating functions we consider are fairly general, in that every step s ∈ S is weighted by an element ω s of some field K of characteristic 0. In general, we will think of the ω s as independent indeterminates. In this case, K is the fraction field Q(ω s , s ∈ S). Of course, one can then specialize the ω s in various ways. The length of the walks is taken into account by an indeterminate t. In particular, the generating function of excursions is

E := ω s1 • • • ω sn t n ,
where the sum runs over all excursions (s 1 , s 2 , . . . , s n ). Clearly, we could incorporate the weight t in the step weights ω s , upon replacing ω s by tω s , but we find more convenient to keep the variable t separate. If min S = -b and max S = a, we assume that ω -b and ω a are non-zero. If d divides all the elements of S, the excursion generating function is unchanged (up to a renaming of the weights ω s ) if we replace each s ∈ S by s/d. Thus we can always assume that the elements of S are relatively prime. Also, if (s 1 , s 2 , . . . , s n ) is an excursion, (-s n , . . . , -s 2 , -s 1 ) is also an excursion, with steps in -S. Thus the excursion series obtained for S and -S coincide, up to a renaming of the weights ω s .

In the expression of E given below (Proposition 1), an important role is played by the following term, which encodes the steps of S:

P (u) = s∈S ω s u s , ( 3
)
where u is a new indeterminate. This is a Laurent polynomial in u with coefficients in K. If min S = -b, we define

K(u) = u b (1 -tP (u)) . (4)
This is now a polynomial in u with coefficients in ) Exactly b of these roots, say U 1 , . . . , U b , are finite at t = 0. These roots are actually formal power series in t 1/b . We call then the small roots of K. The a other roots, U b+1 , . . . , U a+b , are the large roots of K. They are Laurent series in t 1/a , and their first term is ct -1/a , for some c = 0. Note that K(u) factors as

K(u) = u b (1 -tP (u)) = -tω a a+b i=1 (u -U i ) ,
so that the elementary symmetric functions of the U i 's are:

e i (U) = (-1) i ω a-i ω a - 1 tω a χ a=i , (5)
with U = (U 1 , . . . , U a+b ). We refer to [START_REF] Stanley | Enumerative combinatorics[END_REF]Ch. 7] for generalities on symmetric functions.

Unbounded excursions

At least three different approaches have been used to count excursions. The first one generalizes the factorization of Dyck paths mentioned at the beginning of the introduction. It yields a system of algebraic equations defining E [START_REF] Duchon | On the enumeration and generation of generalized Dyck words[END_REF][START_REF] Labelle | Langages de Dyck généralisés[END_REF][START_REF] Labelle | Generalized Dyck paths[END_REF][START_REF] Merlini | Underdiagonal lattice paths with unrestricted steps[END_REF]. The factorization differs from one paper to another. To our knowledge, the simplest, and most systematic one, appears in [START_REF] Duchon | On the enumeration and generation of generalized Dyck words[END_REF].

A second approach [START_REF] Gessel | A factorization for formal Laurent series and lattice path enumeration[END_REF] relies on a factorization of unconstrained walks taking their steps in S, and on a similar factorization of formal power series. The expression of E that can be derived from [START_REF] Gessel | A factorization for formal Laurent series and lattice path enumeration[END_REF] (by combining Proposition 4.4 and the proof of Proposition 5.1) coincides with the expression obtained by the third approach, which is based on a step by step construction of the walks [START_REF] Bousquet-Mélou | Linear recurrences with constant coefficients: the multivariate case[END_REF][START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF]. This expression of E is given in (6) below. We repeat in Section 3 the proof of (6) published in [START_REF] Bousquet-Mélou | Linear recurrences with constant coefficients: the multivariate case[END_REF], as it will be extended later to count bounded excursions.

Proposition 1. The generating function of excursions is algebraic over K(t) of degree at most d a,b = a+b a . It can be written as:

E = (-1) b+1 tω -b b i=1 U i = (-1) a+1 tω a a+b i=b+1 1 U i , (6)
where U 1 , . . . , U b (resp. U b+1 , . . . , U a+b ) are the small (resp. large) roots of the polynomial K(u) given by (4). The quantity defined by

D(t, z) = I⊂ a+b , |I|=a (1 + (-1) a ztω a U I ) , (7)
with a + b = {1, 2, . . . , a + b} and

U I = i∈I U i ,
is a polynomial in t and z with coefficients in K, of degree d a,b in z, satisfying D(t, E) = 0.

Once the expression ( 6) is established, the other statements easily follow. Indeed, the second expression of E shows that D(t, E) = 0. Moreover, the expression of D(t, z) is symmetric in the roots U 1 , . . . , U a+b , so that its coefficients belong to K(t). More precisely, the form (5) of the elementary symmetric functions of the U i 's shows that D(t, z) is a Laurent polynomial in t. But the valuation of U i in t is at least -1/a, and this implies that D(t, z) is a polynomial in t.

Clearly, the degree of D(t, z) in z is d a,b = a+b a . Thus the excursion generating function E has degree at most d a,b . We prove in Section 6 that D(t, z) is actually irreducible in the two following cases:

• S = -b, a and ω -b , . . . , ω a are independent indeterminates (the generic case),

• S = {-b, a} with ω -b = ω a = 1 and a and b coprime (two-step excursions).

As shown by Example 2 below, D(t, z) is not always irreducible.

An algebraic equation for E. As argued above, D(t, z) is a polynomial in t and z that vanishes for z = E. However, its expression [START_REF] Carré | Plethysm of elementary functions[END_REF] involves the series U i , while one would prefer to obtain an explicit polynomial in t and z. Recall that the series U i are only known via their elementary symmetric functions [START_REF] Bousquet-Mélou | Linear recurrences with constant coefficients: the multivariate case[END_REF]. How can one compute a polynomial expression of D(t, z)?

The approaches based on resultants or Grbner bases become very quickly ineffective.

In the generic case where S = -b, a and the weights ω s are indeterminates, K(u) is the general polynomial of degree a + b in u, and the problem can be rephrased as follows: Take n = a + b variables u 1 , . . . , u n , and expand the polynomial

Q(z) = |I|=a (1 -zu I ) (8)
in the basis of elementary symmetric functions of u 1 , . . . , u n . For instance, for a = 2 and b = 1, z 3 (e 3,3 + e 4,1,2 ) + z 4 e 4 (e 3,4,2 + z 6 e 4,4,4 . (9) Using the standard notation for plethysm [START_REF] Stanley | Enumerative combinatorics[END_REF]Appendix 2], the polynomial Q(z) reads

Q(z) = (1 -zu 1 u 2 )(1 -zu 1 u 3 )(1 -zu 2 u 3 ) = 1 -z(u 1 u 2 + u 1 u 3 + u 2 u 3 ) + z 2 (u 2 1 u 2 u 3 + u 1 u 2 2 u 3 + u 1 u 2 u 2 3 ) -z 3 (u 1 u 2 u 3 ) 2 = 1 -ze 2 + z 2 e 3,1 -z 3 e 3,3 , while for a = b = 2, Q(z) = 1 -ze 2 + z 2 (e 3,1 -e 4 ) -
Q(z) = d a,b k=0 (-z) k e k [e a ].
This shows that, in the generic case, the problem of expressing D(t, z) as a polynomial in t and z is equivalent to expanding the plethysms e k [e a ] in the basis of elementary symmetric functions, for an alphabet of n = a + b variables. Unfortunately, there is no general expression for the expansion of e k [e a ] in any standard basis of symmetric functions, and only algorithmic solutions exist [START_REF] Carré | Plethysm of elementary functions[END_REF][START_REF] Chen | Algorithms for plethysm[END_REF]. Most of them expand plethysms in the basis of Schur functions. This is justified by the representation theoretic meaning of plethysm. Still, in our walk problem, the natural basis is that of elementary functions. We have used for our calculations the simple platypus 1 algorithm presented in [START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF], which only exploits the connections between power sums and elementary symmetric functions. This algorithm takes advantage automatically of simplifications occurring in non-generic cases. For instance, when only two steps are allowed, say -b and a, all the elementary symmetric functions of the U i 's vanish, apart from e 0 (U), e a (U) and e a+b (U). It would be a shame to compute the general expansion of e k [e a ] in the elementary basis, and then specialize most of the e i to 0. The platypus algorithm directly gives the expansion of e k [e a ] modulo the ideal generated by the e i , for i = 0, a, a + b. For instance, when a = 2 and b = 1, this would mean that the coefficient of z k in D(t, z) is always a monomial in t. This observation first gave us some hope to find (in the two-step case) a simple description of D(t, z) and, why not, a direct combinatorial proof of D(t, E) = 0. However, this nice pattern does not persist: for a = 3 and b = 5, the coefficient of z 16 in Q(z) contains e 6 8 and e 8 3 e 3 8 . For the sake of completeness, let us describe this platypus algorithm. Take a polynomial L(z) of degree n with constant term 1, and define U 1 , . . . , U n implicitly by

Q(z) ≡ 1 -ze 2 -z 3 e 2 3 ,
L(z) = n k=1 (1 -zU k ).
1 Don't ask me why!

The algorithm gives a polynomial expression of

Q(z) = |I|=a (1 -zU I ) = d k=0 (-z) k e k [e a ](U) with d = n
a and U = (U 1 , . . . , U n ). The only general identity that is needed is the expansion of e a in power sums. This can be obtained from a series expansion via

e a = [z a ] exp   - i≥1 (-z) i i p i   = Φ a (p 1 , . . . , p a ) (10)
for some polynomial Φ a . The rest of the calculation also uses series expansions, and goes as follows:

• compute p i (U) for 1 ≤ i ≤ ad using p i (U) = i[z i ] log(1/L(z)), • compute log Q(z) up to the coefficient of z d using log Q(z) = - i≥1 z i i Φ a (p i (U), p 2i (U), . . . , p ai (U)), (11)
• compute Q(z) up to the coefficient of z d using Q(z) = exp(log Q(z)). Since Q(z) has degree d, the calculation is complete. The identity [START_REF] De Bruijn | The average height of planted plane trees[END_REF] follows from [START_REF] Cohen | Galois groups of trinomials[END_REF] and

log Q(z) = - i≥1 z i i |I|=a U i I = - i≥1 z i i e a (U i 1 , . . . , U i n ).
Given a set of steps S, with max S = a, one obtains a polynomial expression of D(t, z) by applying the platypus algorithm to

L(z) = s∈S ω s ω a z a-s - z a tω a .
If the output of the algorithm is the polynomial Q(z), then D(t, z) = Q((-1) a+1 tω a z).

Example 1: Two step excursions. The simplest walks we can consider are obtained for S = {-b, a} and ω a = ω -b = 1. We always assume that a and b are coprime. If b = 1, Proposition 1 gives E = U/t, where U is the only power series satisfying U = t(1 + U a+1 ). Equivalently, E = 1 + t a+1 E a+1 . This equation can be understood combinatorially by looking at the first visit of the walk at levels a, a -1, . . . , 1, 0, and factoring the walk at these points. Of course, a similar result holds when a = 1.

If a, b > 1, it is still possible, but more difficult, to write directly a system of polynomial equations, based on factorizations of the walks, that define the series E. See for instance [START_REF] Duchon | On the enumeration and generation of generalized Dyck words[END_REF][START_REF] Labelle | Langages de Dyck généralisés[END_REF][START_REF] Labelle | Generalized Dyck paths[END_REF][START_REF] Merlini | Underdiagonal lattice paths with unrestricted steps[END_REF]. It would be interesting to work out the precise link between the components of these systems and the series U i . To compare both types of results, take a = 3 and b = 2. On the one hand, it is shown in [START_REF] Duchon | On the enumeration and generation of generalized Dyck words[END_REF] that E is the first component of the solution of

   E = 1 + L 1 R 1 + L 2 R 2 L 1 = L 2 R 1 + L 3 R 2 R 1 = L 1 R 2 L 2 = L 3 R 1 R 2 = tE L 3 = tE.
On the other hand, Proposition 1 gives E = -U 1 U 2 /t, where U 1 , U 2 are the small roots of u 2 = t(1 + u 5 ). The platypus algorithm gives D(t, E) = 0 with

D(t, z) = 1 -z + t 5 z 5 (2 -z + z 2 ) + t 10 z 10 . ( 12
)
This polynomial is irreducible. Similarly, for a = 4 and b = 3, D(t, E) = 0 with

D(t, z) = 1 -z + t 7 z 7 5 -4 z + z 2 + 3 z 3 -z 5 + z 6 + t 14 z 14 10 -6 z + 3 z 2 + 5 z 3 -z 4 + z 5 + t 21 z 21 10 -4 z + 3 z 2 + z 3 -z 4 + t 28 z 28 5 -z + z 2 -z 3 + z 35 t 35 . ( 13
)
We prove in Section 6 that, in the case of two step walks, D(t, z) is always irreducible. That is, the degree of E is exactly a+b a . Example 2: Playing basket-ball with A. and Z. In a recent paper [START_REF] Ayyer | The number of [old-time] basketball games with final score n : n where the home team was never losing but also never ahead by more than w points[END_REF], the authors consider excursions with steps in {±1, ±2}, where the steps ±2 have length 2 rather than 1. They use factorizations of walks to count excursions (more specifically, excursions of bounded height). This problem fits in our framework by specializing the indeterminates ω s to ω -2 = ω 2 = t, and

ω -1 = ω 1 = 1. Proposition 1 gives E = -U 1 U 2 /t 2 ,
where U 1 and U 2 are the two small roots of u2 = t(t + u + u 3 + tu 4 ). The platypus algorithm yields

D(t, z) = D(t, z)(1 + t 2 z) 2 , (14)
where

D(t, z) = t 8 z 4 -t 4 1 + 2 t 2 z 3 + t 2 3 + 2 t 2 z 2 -1 + 2 t 2 z + 1 ( 15
)
is the minimal polynomial of E. This factorization is an interesting phenomenon, which is not related to the unequal lengths of the steps. Indeed, the same phenomenon occurs when S = {±1, ±2} and all weights are 1. In this case, one finds:

D(t, z) = D(t, z)(1 + tz) 2 with D(t, z) = t 4 z 4 -t 2 (2t + 1)z 3 + t(3t + 2)z 2 -(2t + 1)z + 1,
so that the excursion generating function has degree 4 again. The factorization of D(t, z) is due to the symmetry of the set of steps. For each set of steps S such that S = -S and weights ω s such that ω s = ω -s , the polynomial P (u) given by ( 3) is symmetric in u and 1/u. In particular, a = b. This implies that the small and large roots of 1 -tP (u) can be grouped by pairs: U a+1 = 1/U 1 , . . . , U 2a = 1/U a . In particular, if a is even, the polynomial D(t, z) contains the factor (1 + tω a z) at least a a/2 times. In the basket-ball case (a = 2), this explains the factor (1 + tz) 2 occurring in D(t, z). More generally, we prove in Section 7 that if S is symmetric, with symmetric weights, then the degree of E is at most 2 a , where a = max S.

Excursions of bounded height

We now turn our attention to the enumeration of excursions of height at most k. These are walks on a finite directed graph, so that the classical transfer matrix method applies 2 . The vertices of the graph are 0, 1, . . . , k, and there is an arc from i to j if j -i ∈ S. The adjacency matrix of this graph is

A (k) = (A i,j ) 0≤i,j≤k with A i,j = ω j-i if j -i ∈ S, 0 otherwise. ( 16
)
By considering the nth power of A (k) , it is easy to see [START_REF] Stanley | Enumerative combinatorics[END_REF]Ch. 4] that the series E (k) counting excursions of height at most k is the entry (0, 0) in (1 -tA (k) ) -1 . The translational invariance of our step system gives

E (k) = F k F k+1
where F 0 = 1 and F k+1 is the determinant of 1 -tA (k) . The size of this matrix, k + 1, grows with the height. As was already observed in [START_REF] Banderier | Combinatoire analytique des chemins et des cartes[END_REF], the series counting walks confined in a strip of fixed height can also be expressed using determinants of size a + b, where a = max S and -b = min S. However, the expressions given in the above reference are heavy. A different route yields determinants that are Schur functions in the series U i (recall that these series are the roots of the polynomial K(u) given by ( 4)). This was shown in [START_REF] Bousquet-Mlou | Culminating walks: enumerative properties and random generation[END_REF] for the enumeration of culminating walks. The case of excursions is even simpler, as it only involves rectangular Schur functions.

Let us recall the definition of Schur functions in n variables x 1 , . . . , x n . Let δ = (n -1, n -2, . . . , 1, 0). For any integer partition λ with at most n parts, λ = (λ 1 , . . . , λ n ) with

λ 1 ≥ λ 2 ≥ • • • ≥ λ n ≥ 0, s λ (x 1 , . . . , x n ) = a δ+λ a δ , with a µ = det x µj i 1≤i,j≤n . (17)
Proposition 2. The generating function of excursions of height at most k is

E (k) = F k F k+1 = (-1) a+1 tω a s k a (U) s (k+1) a (U)
where U = (U 1 , . . . , U a+b ) is the collection of roots of the polynomial K(u) given by (4), and

F k+1 = det(1 -tA (k)
) where A (k) is the adjacency matrix [START_REF] Kennedy | The distribution of the maximum Brownian excursion[END_REF]. In particular,

F k = (-1) k(a+1) (tω a ) k s k a (U). ( 18
)
This proposition is proved in Section 4 in two different ways. In Section 5, we derive from the Schur expression of F k that these polynomials satisfy a linear recurrence relation. Equivalently, the generating function k F k z k is a rational function of t and z. Proposition 3. The generating function of the polynomials F k is rational, and can be written as k≥0

F k z k = N (t, z) D(t, z)
where D(t, z) is given by [START_REF] Carré | Plethysm of elementary functions[END_REF], and N (t, z) has degree a+b a -a -b in z. Moreover,

D(t, E) = 0 and N (t, E) = 0.
In other words, the sequence F k satisfies a linear recurrence relation of the form (1), of order d a,b = a+b a , valid for k > a+b a -a -b (with F i = 0 for i < 0). This proposition follows from Proposition 4, which deals with the generating function of rectangular Schur functions of height a: for symmetric functions in n variables,

k s k a z k = P (z) Q(z) (19)
where Q(z) is given by ( 8) and has degree n a , while P (z) has degree n a -n. Computational aspects. We have shown in Section 2.1 that, given the step set S, the polynomial D(t, z) can be computed via the platypus algorithm. One way to determine the numerator N (t, z) is to compute F k explicitly (e.g. as the determinant of (1 -tA (k) )) for k ≤ δ := a+b a -a -b, and then to compute N (t, z) = D(t, z) k F k z k up to the coefficient of z δ .

In the generic case, computing the generating function of the polynomials F k boils down to computing the generating function [START_REF] Labelle | Generalized Dyck paths[END_REF]. Again, the platypus algorithm can be used to determine Q(z) in terms of the elementary symmetric functions. In order to determine P (z), we express the Schur functions s k a , for k ≤ δ := n a -n, in the elementary basis. This can be done using the dual Jacobi-Trudi identity (see Section 5 for details). One finally obtains P (z) by expanding the product Q(z) k s k a z k in the elementary basis up to order δ. For instance, for

a = b = 2, k≥0 s k a z k = 1 -z 2 e 4 Q(z) ,
where Q(z) is given by [START_REF] Cohen | The Galois group of a polynomial with two indeterminate coefficients[END_REF]. More values of P (z) are given in Section 7.2. Let us now revisit the examples of Section 2.1.

Example 1: Two step excursions. When S = {a, -1}, one has D(t, z) = 1 -z + t a+1 z a+1 . The polynomials F k satisfy the recursion F k = F k-1 -t a+1 F k-a-1 , which can be understood combinatorially using Viennot's theory of heaps of pieces [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF]. Via this theory, F k appears as the generating function of trivial heaps of segments of length a on the line 0, k , each segment being weighted by -t a+1 . The recursion is valid for k ≥ 1, with F 0 = 1 and F i = 0 for i < 0. The generating function of the F k 's is k≥0

F k z k = 1 1 -z + t a+1 z a+1 .
When a = 3 and b = 2, the minimal polynomial of the excursion series E is given by ( 12) and the generating function of the polynomials F k is found to be k≥0

F k z k = 1 + t 5 z 5 1 -z + t 5 z 5 (2 -z + z 2 ) + t 10 z 10 .
For a = 4 and b = 3, we refer to [START_REF] Duchon | On the enumeration and generation of generalized Dyck words[END_REF] for the minimal polynomial D(t, z) of E, and k≥0 F k z k = 1 + t 7 z 7 4 + z 3 + z 4 + t 14 z 14 6 + z 3 + 4 t 21 z 21 + t 28 z 28 D(t, z) .

Example 2: Basket-ball again.

For S = {±1, ±2} with ω -2 = ω 2 = t, ω -1 = ω 1 = 1, k≥0 F k z k = 1 -t 2 z (1 + t 2 z) (1 -z(1 + 2t 2 ) + z 2 t 2 (3 + 2t 2 ) -z 3 t 4 (1 + 2 t 2 ) + z 4 t 8 )
.

The denominator is not irreducible. Its second factor is the minimal polynomial of E, see [START_REF] Gessel | A factorization for formal Laurent series and lattice path enumeration[END_REF]. Moreover, comparing to [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF] shows that N (t, z) and D(t, z) have a factor (1 + t 2 z) in common.

A similar phenomenon occurs for S = {±1, ±2} but now ω s = 1 for all s. In this case, k≥0

F k z k = 1 -tz (1 + zt) (1 -z (1 + 2 t) + t (2 + 3 t) z 2 -t 2 (1 + 2 t) z 3 + z 4 t 4 )
.

Again, the minimal polynomial of E is the second factor of the denominator, and N (t, z) and D(t, z) have a factor (1 + tz) in common.

Enumeration of unbounded excursions

Here we establish the expression (6) of the excursion generating function E. The proof is based on a step-by step construction of non-negative walks with steps in S, and on the so-called kernel method. This type of argument is by no means original. The proof that we are going to present can be found in [5, Example 3], then in [START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF], and finds its origin in [17, Ex. 2.2.1.4 and 2.2. 1.11]. The reason why we repeat the proof is because it will be adapted in Section 4 to count excursions of bounded height.

Let W be the set of walks that start from 0, take their steps in S, and always remain at a non-negative level. Let W (t, u) be their generating function, where the variable t counts the length, the variable u counts the final height, and each step s ∈ S is weighted by ω s :

W (t, u) = (s1,s2,...,sn)∈W ω s1 • • • ω sn t n u s1+•••+sn .
We often denote W (t, u) ≡ W (u), and use the notation W h for the generating function of walks of W ending at height h:

W (t, u) = h≥0 u h W h where W h = (s 1 ,s 2 ,...,sn )∈W s 1 +•••+sn=h ω s1 • • • ω sn t n .
A non-empty walk of W is obtained by adding a step of S at the end of another walk of W. However, we must avoid adding a step i to a walk ending at height j, if i + j < 0. This gives

W (u) = 1 + t s∈S ω s u s W (u) -t i∈S,j≥0 i+j<0
ω i u i+j W j .
Let min S = -b. Rewrite the above equation so as to involve only non-negative powers of u:

u b (1 -tP (u))W (u) = u b -t b h=1 u b-h i∈S,j≥0 i+j=-h ω i W j , (20)
with P (u) = s∈S ω s u s . The coefficient of W (u) is the kernel K(u) of the equation, given in (4).

As above, we denote by U 1 , . . . , U b (resp. U b+1 , . . . , U a+b ) the roots of K(u) that are finite (resp. infinite) at t = 0. For 1 ≤ i ≤ b, the series W (U i ) is well-defined (it is a formal power series in t 1/b ). The left-hand side of ( 20) vanishes for u = U i , with i ≤ b, and so the right-hand side vanishes too. But the right-hand side is a polynomial in u, of degree b, leading coefficient 1, and it vanishes at u = U 1 , . . . , U b . This gives

u b (1 -tP (u))W (u) = b i=1 (u -U i ).
As the coefficient of u 0 in the kernel is -tω -b , setting u = 0 in the above equation gives the generating function of excursions:

E = W (0) = (-1) b+1 tω -b b i=1 U i .
This is the first expression in [START_REF] Bousquet-Mlou | Culminating walks: enumerative properties and random generation[END_REF]. The second follows using

U 1 • • • U a+b = (-1) a+b ω -b /ω a (21)
(see ( 5)).

Remark. There exists an alternative way to solve [START_REF] Merlini | Underdiagonal lattice paths with unrestricted steps[END_REF], which does not exploit the fact that the right-hand side of ( 20) has degree b in u. This variant will be useful in the enumeration of bounded excursions. Write

Z -h = i∈S,j≥0 i+j=-h ω i W j ,
so that the right-hand side of (20) reads

u b -t b h=1 u b-h Z -h .
This term vanishes for u = U 1 , . . . , U b . Hence the b series Z -1 , . . . , Z -b satisfy the following system of b linear equations:

For U = U i , with 1 ≤ i ≤ b, b h=1 U b-h Z -h = U b /t.
In matrix form, we have MZ = C/t, where M is the square matrix of size b given by

M =      U b-1 1 U b-2 1 • • • U 1 1 1 U b-1 2 U b-2 2 • • • U 1 2 1 . . . . . . U b-1 b U b-2 b • • • U 1 b 1     
, Z is the column vector (Z -1 , . . . , Z -b ), and C is the column vector (U b 1 , . . . , U b b ). The determinant of M is the Vandermonde in U 1 , . . . , U b , and it is non-zero because the U i are distinct. We are especially interested in the unknown Z -b = ω -b E. Applying Cramer's rule to solve the above system yields

Z -b = (-1) b+1 t det(U b-j+1 i ) 1≤i,j≤b det(U b-j i ) 1≤i,j≤b .
The two determinants coincide, up to a factor U 1 . . . U b , and we finally obtain

E = Z -b ω -b = (-1) b+1 tω -b U 1 • • • U b .

Enumeration of bounded excursions

As argued in Section 2.2, the generating function of excursions of height at most k is

E (k) = F k F k+1 , (22)
where

F k+1 = det(1 -tA (k)
) and A (k) is the adjacency matrix ( 16) describing the allowed steps in the interval 0, k . In order to prove Proposition 2, it remains to establish the expression [START_REF] Labelle | Langages de Dyck généralisés[END_REF] of the polynomial F k as a Schur function of U 1 , . . . , U a+b . We give two proofs. The first one uses the dual Jacobi-Trudi identity to identify F k as a Schur function. The second determines E (k) in terms of Schur functions via the kernel method, and the Schur expression of F k then follows from ( 22) by induction on k (given that F 0 = 1).

First proof via the Jacobi-Trudi identity. The dual Jacobi-Trudi identity expresses Schur functions as a determinant in the elementary symmetric functions e i [26, Cor. 7.16.2]: for any partition λ,

s λ = det e λ ′ j +i-j 1≤i,j≤λ1
, where λ ′ is the conjugate of λ. Apply this identity to λ = (k + 1) a . Then λ ′ = a k+1 and

s (k+1) a = det J (k) with J (k) = (e a+i-j ) 1≤i,j≤k+1 .
Now, specialize this to symmetric functions in the a + b variables V = (V 1 , . . . , V a+b ) where V i = -U i for all i. By ( 5), the elementary symmetric functions of the V i are

e i (V) = ω a-i ω a - 1 tω a χ i=a = - 1 tω a (χ i=a -tω a-i ) .
This shows that the matrix J (k) coincides with -(1 -tA (k) )/(tω a ), so that

s λ (V) = (-tω a ) -(k+1) F k+1 = (-1) a(k+1) s λ (U),
since s λ is homogeneous of degree a(k + 1). This gives the Schur expression of F k+1 .

Second proof via the kernel method. We adapt the step by step approach of Section 3 to count excursions of height at most k. Let W (k) (t, u) ≡ W (k) (u) be the generating function of non-negative walks of height at most k. As before, we count them by their length (variable t) and final height (u) with multiplicative weights ω s on the steps. We use notations similar to those of Section 3. When constructing walks step by step, we must still avoid going below level 0, but also above level k. This yields:

W (k) (u) = 1 + t s∈S ω s u s W (k) (u) -t i∈S,j≥0 i+j>k or i+j<0 ω i u i+j W (k) j ,
or, with min S = -b,

u b (1 -tP (u))W (k) (u) = u b -t k+a h=k+1 u b+h Z (k) h -t b h=1 u b-h Z (k) -h , (23)
where

Z (k) h = i∈S,j≥0 i+j=h ω i W (k) j .
The series W (k) (u) is now a polynomial in u (with coefficients in the ring of power series in t). This implies that any root U i of the kernel K(u) = u b (1 -tP (u)) can be legally substituted for u in [START_REF] Schinzel | On reducible trinomials[END_REF]. The right-hand side and the left-hand side then vanish, and provide a system of a + b linear equations satisfied by the

Z h : For U = U i , with 1 ≤ i ≤ a + b, k+a h=k+1 U b+h Z (k) h + b h=1 U b-h Z (k) -h = U b /t.
In matrix form, we have M (k) Z (k) = C/t, where M (k) is the square matrix of size a + b given by

M (k) =      U a+b+k 1 U a+b+k-1 1 • • • U b+k+1 1 U b-1 1 U b-2 1 • • • 1 U a+b+k 2 • • • • • • 1 . . . . . . U a+b+k a+b U a+b+k-1 a+b • • • U b+k+1 a+b U b-1 a+b U b-2 a+b • • • 1      , Z (k) is the column vector (Z (k) k+a , . . . , Z (k) k+1 , Z (k)
-1 , . . . , Z

-b ), and C is the column vector (U b 1 , . . . , U b a+b ). We are especially interested in the series

Z (k) -b = ω -b E (k) . Cramer's rule now gives Z (k) -b = (-1) b+1 t det(U a+b+k i , . . . , U b+k+1 i , U b i , U b-1 i , . . . , U i ) 1≤i≤a+b det M (k) , (24)
provided det M (k) = 0. In view of the definition [START_REF] Knuth | The art of computer programming[END_REF] of Schur functions, this yields:

E (k) = Z (k) -b ω -b = (-1) b+1 tω -b U 1 • • • U a+b s k a (U) s (k+1) a (U)
.

Thanks to [START_REF] Osada | The Galois groups of the polynomials X n + aX l + b[END_REF], the generating function of excursions of height at most k can finally be rewritten

E (k) = (-1) a+1 tω a s k a (U) s (k+1) a (U)
.

Using [START_REF] Prodinger | The kernel method: a collection of examples[END_REF], we finally express the polynomial F k in terms of Schur functions:

F k = 1 E (0) • • • E (k-1) = (-1) k(a+1) (tω a ) k s k a .
We still have to prove that the determinant of M (k) is non-zero. Whether M (k) is singular or not, the following variant of (24) remains valid:

det M (k) Z (k) -b = (-1) b+1 t det(U a+b+k i , . . . , U b+k+1 i , U b i , U b-1 i , . . . , U i ) 1≤i≤a+b = (-1) b+1 t V (U) s k a (U) a+b i=1 U i ,
where V (U) denotes the Vandermonde in the U i 's. Since these series are distinct and non-zero, this shows that if det M (k) = 0, that is, s (k+1) a (U) = 0, then s k a (U) = 0 as well. But this would finally imply s 0 (U) = 0, while s 0 (U) = 1. Thus det M (k) = 0, and the second proof of Proposition 2 is now complete.

Generating functions of rectangular Schur functions

We will now prove Proposition 3, which connects the (algebraic) excursion generating function E to the polynomials F k occurring in the (rational) generating function E (k) counting excursions of height at most k. Now that we have expressed F k as a Schur function [START_REF] Labelle | Langages de Dyck généralisés[END_REF], Proposition 3 is a specialization of the following result. so that P (z) has degree n a -n exactly. It remains to determine P (1/u J ), for |J| = a. We specialize the expression (29) of P (z) to the case z = 1/u J . The only permutations σ having a non-zero contribution are those such that σ( a ) = J. Every such permutation σ can be written in a unique way σ = πτ σ J , where σ J is the shortest permutation sending a to J, and τ (resp. π) is any permutation on J (resp. c J). Thus, if J = {j 1 , . . . , j a } with j 1 < . . . < j a and c J = {k 1 , . . . , k b } with k 1 < . . . < k b , we have

P (1/u J ) = |I|=a,I =J (1 -u I /u J ) ε(σ J ) V n τ ∈S(J) ε(τ )τ u n-1 j1 • • • u b ja π∈S( c J) ε(π)π u b-1 k1 • • • u 0 k b = |I|=a,I =J (1 -u I /u J ) ε(σ J ) V n u b J V (J) V ( c J),
where V (J) denotes the Vandermonde in the variables u j , j ∈ J. This is easily seen to be equivalent to [START_REF] Stanley | Enumerative combinatorics[END_REF].

We can now complete the proof of Proposition 3. We combine the Schur expression of F k given in Proposition 2 with Proposition 4. Set n = a + b. The indeterminates u 1 , . . . , u a+b are specialized to U 1 , . . . , U a+b , and we obtain:

k≥0 F k z k = P ((-1) a+1 tω a z) Q((-1) a+1 tω a z) = N (t, z) D(t, z)
where D(t, z) = Q((-1) a+1 tω a z) is exactly the polynomial [START_REF] Carré | Plethysm of elementary functions[END_REF]. The dominant coefficient of P (z), given by (31), does not vanish when specializing u i to U i . Thus N (t, z) = P ((-1) a+1 tω a z) has degree n a -n exactly. We have already seen that the excursion generating function E given in Proposition 1 satisfies D(t, E) = 0. Now, since E = (-1) a+1 /(tω a U J ), with J = {b+1, . . . , a+b},

N (t, E) = P (1/U J ) = |I|=a,|I∆J|≥4
(1 -U I /U J ) by [START_REF] Stanley | Enumerative combinatorics[END_REF]. Recall that U b+1 , . . . , U a+b are the roots of K(u) with valuation -1/a, while the b other roots have valuation 1/b. This implies that U I = U J for I = J, so that N (t, E) = 0.

The degree of the excursion generating function

We conclude this paper by proving that the results stated in Section 2 are, in a sense, optimal. We have defined in [START_REF] Carré | Plethysm of elementary functions[END_REF] a polynomial D(t, z), of degree d a,b = a+b a , which satisfies D(t, E) = 0 and is the denominator of the rational series k F k z k . We prove that D(t, z) is irreducible in the following two cases:

• S = -b, a and ω -b , . . . , ω a are independent indeterminates, • S = {-b, a} with ω -b = ω a = 1 and a and b coprime.

In the first case, the kernel K(u) is essentially the general algebraic equation of degree a + b, so that the result may be predictable. The idea is that there are no non-trivial relations between the series U i . The second case is less obvious. Proposition 5. In the above two cases, the generating function of excursions with steps in S is algebraic of degree d a,b = a+b a . Its minimal polynomial is given by [START_REF] Carré | Plethysm of elementary functions[END_REF]. Recall, from Example 2 in Section 2.1, that E has sometimes degree less than d a,b (for instance when S = {±1, ±2} with weights 1).

The key tool is the study of the Galois group of the polynomial K(u). We begin with a condition implying the irreducibility of D(t, z). Lemma 6. Let S be a finite set of steps with weights ω s ∈ K. Let a = max S, -b = min S and n = a + b. Let K(u) be the polynomial in u, with coefficients in K(t), defined by (4).

If the Galois group of K(u) over K(t), seen as a permutation group of the U ′ i s, is the full symmetric group S n , then the product U 1 . . . U b of the small roots of K(u) has degree d a,b = a+b a . In other words, the polynomial D(t, z) given by (7) is irreducible. Proof. The extension K(t, U 1 , . . . , U n ) of K(t) is normal by construction, and separable since we have assumed K to be of characteristic 0. Assume that the Galois group of K(t, U 1 , . . . , U n ) over K(t) is S n . By the main result of Galois theory, the correspondence Φ between subgroups G of S n and sub-extensions

L of K(t, U 1 , . . . , U n ) defined by Φ(G) = L = {x ∈ K(t, U 1 , . . . , U n ) : σ(x) = x for all σ ∈ G} is bijective. Its inverse is given by Φ -1 (L) = G = {σ ∈ S n : σ(x) = x for all x ∈ L}.
Moreover, the degree of K(t, U 1 , . . . , U n ) over L is |G|.

In particular, let L = K(t, U 1 • • • U b ) be the extension of K(t) generated by the product of the small roots. Given that U 1 , . . . , U b have valuation 1/b in t, while U b+1 , . . . , U a+b have valuation -1/a, the only permutations σ of S n that leave U 1 . . . , U b unchanged are those that fix the set b . That is, Φ

-1 (L) ≃ S b × S a . Thus K(t, U 1 , . . . , U n ) has degree a!b! over L, degree (a + b)! over K(t), so that L = K(t, U 1 • • • U b ) has degree a+b a over K(t).
We now apply the above lemma to prove Proposition 5. Proof of Proposition 5. In the first case, K(u) is the general equation of degree n = a + b. It is well-known that its Galois group is S n . See for instance [START_REF] Stewart | Galois Theory[END_REF].

In the second case, we want to prove that the Galois group of K(u) = u b -t(1+u a+b ) over Q(t) is S n , with n = a+ b. This has been proved for trinomials u a+b + αu b + β with two indeterminate coefficients α and β (see [START_REF] Smith | General trinomials having symmetric Galois group[END_REF][START_REF] Cohen | The Galois group of a polynomial with two indeterminate coefficients[END_REF]), and for some trinomials with rational coefficients [START_REF] Osada | The Galois groups of the polynomials X n + aX l + b[END_REF][START_REF] Cohen | Galois groups of trinomials[END_REF]. The latter results are of course harder that the former. Given that we could not find any reference dealing with trinomials involving exactly one indeterminate coefficient, we will rely on the strong results obtained for trinomials of Q[u].

We first note that it suffices to prove that the trinomial u b -t 0 (1 + u a+b ) has Galois group S n over Q for some rational number t 0 . Since a and b are coprime, Theorem 8 of [START_REF] Schinzel | On reducible trinomials[END_REF] implies that there exist only finitely many α ∈ Z such that u a+b + αu b + 1 is reducible. Thus we can choose α ∈ Z, coprime with n = a + b, and such that the above trinomial is irreducible. Then by [START_REF] Osada | The Galois groups of the polynomials X n + aX l + b[END_REF]Thm. 1], this trinomial has Galois group S n over Q.

Concluding remarks and questions

The degree of the excursion generating function

We have shown in Section 6 that the degree of E is maximal, equal to a+b a , both in the generic case and in the two-step case. This can be extended to all set steps such that K(u) has at least two (algebraically independent) indeterminate coefficients, using the results of [START_REF] Cohen | The Galois group of a polynomial with two indeterminate coefficients[END_REF].

It would be interesting to study more cases, in particular those involving a symmetry, which reduces the degree. Assume S = -S, and ω -s = ω s for all s ∈ S. In particular, a = b. Then, as discussed in Example 2, the small and large roots of K(u) are simply related by U a+1 = 1/U 1 , . . . , U 2a = 1/U a . This implies that many products

U i1 • • • U ia , with i 1 < • • • < i a , are actually of the form U j1 • • • U j a-2k
for some k > 0. The products that reduce in that way have a minimal polynomial that strictly divides

Q(z) = |I|=a (1 -zU I ).
The non-reducing products U i1 • • • U ia are the 2 a terms U

I = U ±1 1 • • • U ±1 a . Thus Q(z) = ε∈{±1} a
(1 -zU ε ), is a polynomial in z and t that divides Q(z), and vanishes at z = E. Hence in the symmetric case, E has degree at most 2 a .

One could try to study systematically the cases S = -a, a or S = {±1, ±a}. When S = {±1, ±2}, we have seen in Example 2 that E has degree 4. The Galois group G of K(u) = u 2 -t(1 + u) 2 (1 -u + u 2 ) over Q(t) can be seen to isomorphic to the dihedral group D 4 . More precisely, G = {id, (1, 2, 3, 4), [START_REF] Ayyer | The number of [old-time] basketball games with final score n : n where the home team was never losing but also never ahead by more than w points[END_REF][START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF][START_REF] Banderier | Generating functions for generating trees[END_REF][START_REF] Banderier | Combinatoire analytique des chemins et des cartes[END_REF], (1, 3)(2, 4), (1, 2) [START_REF] Banderier | Generating functions for generating trees[END_REF][START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF], [START_REF] Ayyer | The number of [old-time] basketball games with final score n : n where the home team was never losing but also never ahead by more than w points[END_REF][START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF](2, 3), (1, 3), (2, 4)}. The subgroup that leaves U 1 U 2 invariant is the subgroup of index 4 generated by (1, 2) [START_REF] Banderier | Generating functions for generating trees[END_REF][START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF]. This explains why E = -U 1 U 2 /t has degree 4.

The generating function of rectangular Schur functions

We proved in Section 5 that, for symmetric functions in n variables, the generating function of rectangular Schur functions of height a is rational:

k≥0 s k a z k = P (z) Q(z) ,
where Q(z) is given by ( 25) and has degree n a , while P (z) has degree n a -n. We have given two expressions of P (z) in terms of the u i 's (see [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF](30))), and proved that P (1/u J ) has a simple expression [START_REF] Stanley | Enumerative combinatorics[END_REF]. However, we have no expansion of P (z) in symmetric functions, other than We have used the Schur basis rather than the elementary basis because it seems, from these examples, that the coefficient of z i in P (z) is either Schur-positive or Schur-negative. The conversions to Schur functions have been made with the package ACE [START_REF] Veigneau | ACE, an Algebraic Combinatorics Environment for the computer algebra system MAPLE: User's Reference Manual[END_REF].

P (z) =

The height of random excursions

Pick an excursion of length n, uniformly at random. Its height is a random variable H n . For Dyck paths, it is known that H 2n / √ n converges in distribution to a theta law [START_REF] De Bruijn | The average height of planted plane trees[END_REF], which also describes the height of the Brownian excursion [START_REF] Kennedy | The distribution of the maximum Brownian excursion[END_REF]. We expect this to hold for our general excursions as well. One indication of the universality of this law can be given in terms of trees. Via a simple bijection, the height of a random Dyck path of length 2n becomes the height of a random plane tree with n edges. It has been proved that the height of other varieties of trees, like simple trees, also follows, in the limit, a theta law [START_REF] Flajolet | The average height of binary trees and other simple trees[END_REF].

The average height of plane trees -that is, of Dyck paths -was derived in [START_REF] De Bruijn | The average height of planted plane trees[END_REF] from an expression of E (k) that is equivalent to our Schur expression of this series. Is it possible, using the asymptotic tools developed in [START_REF] Banderier | Basic analytic combinatorics of directed lattice paths[END_REF] for unbounded excursions, to work out the law of the height of general excursions by starting from our Schur expression of E (k) ?

1

 1

Figure 1 .

 1 Figure 1. Left: A Dyck path of length 16 and height 4. Right: An excursion (generalized Dyck path) of length 8 and height 7, with steps in S = {-3, 5}. sequence (F k ) k satisfy a linear recurrence relation? Of what order? How can one determine this recursion? Note that any linear recursion of order d, of the form d

5 + z 6 e 2 e 2 5 -z 7 e 2 2 e 2 5 + z 10 e 4 5 .+2z 8 e 5 e 5 7 -2z 9 e 2 5 e 5 7 +z 10 e 3 5 e 5 7 -z 11 e 4 5 e 5 7 +3z 14 e 10 7 -z 15 e 5 e 10 7 +2z 16 e 2 5 e 10 7 -z 21 e 15 7 .

 555577777 while for a = 2 and b = 3, Q(z) ≡ 1 -ze 2 -2z 5 e 2 and for a = 5 and b = 2, Q(z) ≡ 1-ze 5 -3z 7 e 5 7 From the above examples, one may suspect that, in the two-step case, the coefficient of z k in Q(z) is always a monomial. Going back to the polynomial D(t, z), and given that e a (U) = (-1) a+1 tω a and e a+b (U) = (-1) a+b ω -b ω a ,

Proposition 4 .

 4 Let 1 ≤ a ≤ n. The generating function of rectangular Schur functions of length a in n variables u 1 , . . . , u n is k≥0 s k a z k = P (z) Q(z)

(- 1 ) 2 = 1 -s 4 z 2 . 5 + (s 53 3 2 2 + s 4 3 2 3 + s 4 2 3 3 1 ) z 6 -2 s 54 2 3 2 2 z 7 + (s 5 3 3 3 + s 64 3 3 2 + s 5 2 4 3 2 ) z 8 -(s 5 5 2 + s 74 5 ) z 9 -s 6 2 5 2 4 2 z 10 + (s 6 4

 1212523167328259104 j e j [e a ] s k a , which comes directly from the fact that P (z) = Q(z) k≥0 s k a z k . It would be interesting to find a simpler expression for the coefficients of P (z). The term (-1) j , in particular, leaves hope for possible simplifications, which may in turn allow us to compute P (z) more efficiently. Let us give the expression of P for a few values of a and n: for a = 2 and n = 4,P (z) = 1 -e 4 zFor a = 2 and n = 5,P (z) = 1 -e 4 z 2 + e 5,1 z 3 -e 5 2 z 5 = 1 -s 1 4 z 2 + s 2,1 4 z 3 -s 2 5 z 5 .For a = 3 and n = 6,P (z) = 1 -s 21 4 z 2 + (s 2 4 1 + s 321 4 ) z 3 -s 3 2 2 2 1 2 z 4 -(s3 5 + s 52 5 ) z 54 + s 765 4 ) z 11 -s 76 4 5 z 12 + s 7 6 z 14 .

In language theoretic terms, the words of S * that encode these bounded excursions are recognized by a finite automaton.

Acknowledgements. I am indebted to Alain Lascoux and Christophe Carr for providing efficient programs to compute plethysms. I also thank Alain Salinier for interesting e-discussions about the Galois groups of trinomials, and for pointing Reference [23].

where

has degree n a in z and P (z) has degree n a -n. (We have used the notation u I = i∈I u i .) Moreover, for all J of cardinality a,

Proof. Let us write n = a + b. By definition of Schur functions,

where

where σ acts on functions of u 1 , . . . , u n by permuting the variables:

where Q(z) is given by [START_REF] Stanley | Enumerative combinatorics[END_REF] and

The above expression suggests that the degree of P (z) could be as large as n a -1, while we claim it is only n a -n. To explain this gap, it suffices to notice that the determinant (27) vanishes for k ∈ {-n + 1, -n + 2, . . . , -1}. Thus the sum over k in [START_REF] Veigneau | ACE, an Algebraic Combinatorics Environment for the computer algebra system MAPLE: User's Reference Manual[END_REF] could just as well start at k = -n + 1, giving:

This provides the following alternative expression of P (z):

The right-hand side is a polynomial in z of degree (at most) n a -1, and this polynomial is the product of P (z) and z n-1 . This shows that P (z) has degree at most n a -n. Moreover, by extracting the coefficient of z ( n a )-1 in the above identity, one finds:

CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France E-mail address: mireille.bousquet@labri.fr


Sylvie Huet
email: sylvie.huet@irstea.fr

Guillaume Deffuant Irstea
email: guillaume.deffuant@irstea.fr

The Leviathan model without gossips and vanity: the richness of influence based on perceived hierarchy

This paper studies a simplified version of the Leviathan model, without gossip and vanity processes. During dyadic meetings, the agents change their opinion about themselves and about their interlocutor. Speakers highly valued by their listeners are more influential. Only due to the asymmetry of the influence function, the model produces several patterns depending on the parameter values, some of which not yet identified in the first Leviathan model study. In particular, in some cases the leaders have a high opinion of other leaders whereas in other cases they have a low one.

The recently proposed Leviathan model [START_REF] Deffuant | The Leviathan model: Absolute dominance, generalised distrust and other patterns emerging from combining vanity with opinion propagation[END_REF] considers a population of agents, each characterized by its opinion (a continuous number between -1 and +1) about each of the agents (including itself), and dynamics of these opinions through processes of opinion propagation and vanity, taking place during random dyadic encounters. This model is very rich in terms of emerging behaviors, and [START_REF] Deffuant | The Leviathan model: Absolute dominance, generalised distrust and other patterns emerging from combining vanity with opinion propagation[END_REF] focuses only on a limited set of parameter values. To go further, we propose here a more complete study of one of the model's basic processes which is the direct opinion propagation (without gossiping). Whereas in many opinion models, the influence increases with the similarity between the agents (homophily [START_REF] Castellano | Statistical physics of social dynamics[END_REF] [START_REF] Byrne | An Overview (and Underview) of Research and Theory within the Attraction Paradigm[END_REF][START_REF] Mark | Culture and Competition: Homophily and Distancing Explanations for Cultural Niches[END_REF][START_REF] Takács | Is There Negative Social Influence? Disentangling Effects of Dissimilarity and Disliking on Opinion Shifts[END_REF] [START_REF] Axelrod | The dissemination of culture a model with local convergence and global polarization[END_REF]), in the Leviathan model, the influence increases with the superiority of the speaker as perceived by the listener (difference between listener's opinion about the speaker and listener's self-opinion). This modelling choice can be grounded in the research in social psychology considering for example [START_REF] Wood | Seeking Pleasure and Avoiding Pain in Interpersonal Relationships[END_REF] or [START_REF] Tost | Power, competitiveness, and advice taking: Why the powerful don't listen[END_REF] who has experimentally shown that people feeling high in power tends to discount other's advice on the contrary those feeling low.

Indeed, complementary to the classical approaches based on homophily, a large body of work considers the influence in terms of credibility of the source [START_REF] Crano | A preliminary investigation of a hyperbolic model of attitude change[END_REF][START_REF] Pornpitakpan | The persuasiveness of source credibility: A critical review of five decades' evidence[END_REF][START_REF] Tormala | Attitude Certainty: A Review of Past Findings and Emerging Perspectives[END_REF]. The influence function of the Leviathan model is a sigmoid logistic model. This model is more classically used as a probabilistic version of a threshold model [START_REF] Young | The Diffusion of Innovations in Social Networks[END_REF] [START_REF] Huet | Taking into account the variations of social network in the mean-field approximation of the threshold behaviour diffusion model[END_REF].

Surprisingly, and even in the absence of vanity and gossip, the model generates a rich variety of patterns and this paper aims at identifying and characterizing them. It is organised as follows. We start by a description of the dynamics. Then, we describe the observed patterns and offer some generalised definitions of their characteristics as well as how they appear during trajectories of the model. We especially point out the link between the influence function parameters, the level of agreement of agents about their respective order and the average sign of the opinion of the population. Finally, we discuss our results and identify some complementary studies to carry out.

Opinion propagation depending on perceived hierarchy

We consider a set of N agents, each agent i is characterised by her list of opinions about the other agents and about herself: (ai,j)1 ≤i,j≤N . We assume ai,j lies between -1 and +1 , or it is undefined (equal to nil) if the agent i never met j and nobody has talked to i about j yet. At initialisation, we suppose that the agents never met, therefore all their opinions are undefined. When opinions change, we always keep them between -1 and +1, by truncating them to -1 if their value is below -1 after the interaction, or to +1 if their value is above +1. The individuals interact in uniformly and randomly drawn pairs (i, j) and at each encounter they try to influence each other on their respective values. We define one iteration, i.e. one time step t →t + 1, as N/2 random pair interactions (each individual interacts 1 time on average during one iteration). To be more precise, one iteration involves the following steps:

Repeat N/2 times: Choose randomly a couple (i,j) Save the opinions which are going to change in temporary variables to ensure the update during the i and j meeting is synchronous Influence(i,j) Influence(j,i)

The influence(i,j) process is:

Influence(i,j) if a ii = nil, a ii ← 0 if a ij = nil, a ij ← 0 )) , ( Random (          ii ji ij ii ii a a p a a ij ij jj ij ij ij v a a p a a       
)) , ( Random (

  

We recognise the equations of opinion influence (or propagation) in which opinions attract each other, but with two differences. The first difference is that the strength of the propagation of opinion is ruled by a parameter ρ multiplied by a function p i,j . Function p i,j implements the hypothesis that the more i perceives j as superior to itself, then the more j is influential on i. It is a logistic function (with parameter σ) of the difference between the opinion of i about j (a i,j ) and the opinion i about herself (a i,i ):

       / exp 1 1 ii ij ij a a p    
p i,j tends to 1 when a i,j -a i,i is close to 2 (i values j higher than herself), and tends to 0 when it is close to -2 (i values j lower than herself). When σis small, p ij rapidly changes from 0 to 1. When σis large, this change is progressive.

If a i,j = nil (j is unknown to i), we assume that i has no opinion because he has not met or hear about j. At the first meeting, we suppose that the a priori about j is neutral and we set a i,j ← 0. Let us also observe that, at the initialisation, an agent has no opinion about herself thus we also set a i,i ← 0 at the first discussion.

The second difference with simple attraction dynamics is the introduction of variable  This variable models the idea that an agent i has no direct access to the opinions of another one (j) and can misunderstand it. To take into account this difficulty, we consider the perception of the agent i as the value a jz more or less a uniform noise drawn between - and + ( is a model parameter). This random addition then corresponds to a systematic error the agents make about the others' opinions. It can be seen as a noise that distorts the perception that i has about j 's opinions. The parameter δ rules the amplitude of this noise. Note that the update is synchronous: every opinion changes occurring during a meeting are computed on the same value of opinions taken at the beginning of a pair meeting.

Finally, the model has 4 parameters:  the number of individuals;  , the reverse of the sigmoidal slope of the propagation coefficient;  , maximum intensity of the noise when someone is alluded to;  ρ, the parameter controlling the intensity of the coefficient of the influence.

2

Exploring the emerging patterns in the parameter space

This section begins by presenting the emerging patterns we can observe from the variation of the parameter values. These patterns can be seen as emerging social orders from the agents' interaction. Then, their properties are studied further using a large experimental design showing they are coupled to form specific trajectories of simulation. A last part point out the relation between parameters of the influence function, the level of agreement of agents on how they order each other, and the sign of the average opinion in the population.

The emerging patterns

The following figures presenting the patterns use a representation in which the opinions of each agent is represented as the row of a N×N square matrix. The element a i,j from line i and column j is the opinion of agent i about agent j. We use colours to code for the opinions: blue for negative and red for positive opinions with light colours meaning that the absolute value is close to 0. In the tests, we consider N=20 agents and ρ=0.8. We distinguish patterns with the following criteria:  The presence of leaders: they are agents about which all agents have a very positive (close to +1) opinion; they are recognizable by the strength of the positive view they benefit from. In our matrix representation, they appear as a red column;  The level of agreement about the agents: agents agree more or less about their peers (the average value of opinions about an agent is called its reputation for sake of simplicity). In our matrix representation, when all the values in a column are close (colors are homogeneous), the level of agreement about the agent of this column is high.  The distribution of reputations represents a more or less skewed hierarchy.

Moreover, we have characterized patterns using the sign of the average opinion of the population as well as the level of agreement on how they perceive each other (do they perceive each other in the same hierarchy), especially when they are leaders. In this latter case, we talk about disagreeing leaders or agreeing leaders.

Using these criteria, we have observed three main groups of patterns: dominance and crisis; disorder; and hierarchy. They are presented in the following.

Dominance and crisis.

Dominance is characterized by the presence of one or two agents with a reputation close to +1, that we call leaders (it can very temporarily increase up to 6 but it does not last) while every other agent has a significantly lower reputation. Fig. 1 shows the various types of dominance we observed plus the crisis in which there is no leader. Crisis (fig. 1a) never appears alone; it alternates with the dominance (fig. 1b). Moreover, various types of dominance can be observed, from negative (fig. 1 b andc) to positive (fig. 1d) as well as some in which leaders agree their respective positions (fig. 1b andd) or disagree (fig. 1c). Fig. 1c illustrates the disagreement between leaders: one can see the most positive leader (more dark red squares) in the center has a neutral opinion (white squares) about the second leader on the right ; the second leader has also an opinion about the first leader which is close to 0 but it has a positive self-opinion.

Disorder. This pattern is characterized by a very weak agreement on each other values of opinion. Fig. 2 shows the two types we observe: (a) the negative disorder; and (b) the positive disorder. The positive disorder seems to exhibit a larger number of positive self-opinion (see the red square on the diagonal from the top left to the bottom right).

Hierarchy in which the distribution of reputations is less bimodal than in dominance patterns and the agreement on reputations is higher than in the disorder. However, as shown in fig. 3, different types can be identified: it can be more negative than positive as in (a) and (b), or more positive than negative as in (c) and (d); leaders can agree as in (b), (c) and (d), or totally disagree and have a negative opinion of each other as in (a). This latter case is not so easily differentiable from dominance with disagreeing leaders. Starting from the various characteristics and types of pattern we observe, we develop a procedure for automatically detecting the patterns and a large experimental design aiming at exploring the parameter space.

2.2

Systematic exploration of the parameter space

An algorithm detecting the pattern types

We build a pattern type detection algorithm based on a minimum number of indicators:

 the average opinion for the definition of the main sign of the pattern ;  the bimodal properties of the distribution of opinions; the number of positive reputation to diagnose the absence of leader;  the average between the maximum and the minimum opinion for an agent that we compare to 2δ in order to diagnose the disorder corresponding to a disagreement level higher than the noise δ ;  the global difference between the maximum and the minimum opinion to qualify the length of the opinion distribution, particularly to distinguish dominance from hierarchy. The pattern identification algorithm is finally the following: Then we compute an experimental design running this diagnosis. The model includes 4 parameters. We fix N, the number of agents to 40, and ρ ruling the intensity of the opinion propagation coefficient to 0.8. This is in order to make tractable results of our study. We vary the other parameters as follows:

 δ, the intensity of noise disturbing the evaluation of other's opinions takes two different values: 0.01, 0.03, 0.05, 0.1, 0.2, 0.3, 0.4;  σ, ruling the slope of the logistic function determining the propagation coefficients takes the values 0.01, 0.03, 0.05, 0.07, 0.1, 0.2, 0.3;

For each set of parameter values, we run the model for 200,000,000 iterations (one iteration corresponding to N/2 random pair interactions), and we repeat this for 10 replicas. We measure every 100,000 iterations a group of values allowing us to make conclusions about the properties of our patterns. The measured values over 10 replicas are averaged into indicator that is used in the next subsection to characterise our patterns.

2.2.2

The properties of patterns

We consider the complementary following indicators: the type of relations between leaders; the average agreement rate; the number of positive reputations; the number of agents thinking they are the best over the whole population. The type of relation between leaders is defined by a minimum disagreement about the leadership between the leaders. The disagreement occurs when they disagree on their respective order (who is the first, who is the second; in most cases the two think they are both the first). If more than 10% of the leaders disagree, we say this is a disagreement (D) type of leadership; on the contrary it is called (A) agreement. The average agreement rate on order corresponds to the average percentage of dyadic meetings over all the meetings during which the two agents disagree about how to order them. Table 1 presents the results we obtained over our experimental design. We globally identified again what we have observed in figures 1 to 3. Few configurations appear in only one execution of the model while we did 10 replicas of the 49 parameter sets. We decided to omit them in the table for sake of clarity. The table 1 confirms that the pattern dominance has one or two leaders even if a negative Hierarchy with disagreeing leaders also appears with 1.0 leader but it is probably a false diagnosis and it appears rarely (0.05%).

The disorder in its positive form is very specific in terms of agreement on order but also in terms of number of agents thinking that they are the best; the two subcatego-ries "Agreeing" and "Disagreeing" leaders are not really relevant since there is no leaders; they do not vary from each other and the "A" modality is very rare, probably due to the threshold chosen for the agreement. The disorder in its negative form is softer; it differs less from the other negative patterns.

Crisis always corresponds to disagreeing leaders (even if they are not positive in this case as for the other patterns).

Hierarchy, whatever its signs is characterized by a higher level of agreement rate on order during meetings. It is more characterized by disagreement between its leaders when the average opinion is positive while it is the contrary for the negative average opinion. Overall, and except the case cited earlier, it shows more leaders than the dominance.

The "disagreement" between leaders corresponds to a smaller number of leaders in case of dominance and negative hierarchy. The negative patterns, crisis, dominance and disorder, whatever the type of relation between leaders, show a lower average agreement rate (between 0.6 and 0.7) than the positive ones.

Table 2. Trajectories (set of patterns appearing during one execution of the model).

Regarding the trajectory sign, we put altogether "positive" and "positive and negative" (*pAndN) when they represent less than 5% of the runs.

Set of patterns appearing in one trajectory

Trajectory sign From our results we also confirm that some patterns are only observable coupled to others in trajectories. Table 2 breaks down these observations. We need 4.9 % of the runs to represent a total parameter set. Let consider the pattern appearing more than 4.9 % and see the average parameter values required to reach them. We distinguish clearly in table 2 three areas: "dominance-disorder-crisis", "dominance-hierarchy" and hierarchy corresponding to the most frequent trajectories.

Relation between leaders % of runs

Trajectories in the parameter space

In order to understand the richness of the model, we locate these three trajectories into the parameter space in table 3 with colour codes.

From the figures 2, we know that the empty bottom left cases of the table 3 corresponds to Disorder (negative for σ 0.01 and δ 0.2; positive for σ 0.01 and δ 0.4). Disorder has not been identified as a main trajectory in the previous phase due to its low frequency of appearance. However, it is probably due to the diagnosis which is very demanding on the level of disorder: that is probable this level changes a lot during a simulation and only a part of measures satisfied the threshold of 2δ as the minimum average difference of opinion about one agent. Table 3. Main trajectories in the parameter space: light orange is Dominance-Hierarchy positive; blue is Dominance-Disorder-Crisis; brown is Dominance-Hierarchy positive and « positive and negative »; rose is Hierarchy and Dominance-Hierarchy positive; red is Hierarchy. The white bottom left area corresponds to the pattern disorder in its negative shape then in its positive shape when δ increases.

The link between agreement and sign

We observed in table 1 that the average rate of agreement is a good indicator to distinguish negative from positive patterns. Fig. 4 shows this indicator in the parameter space represented on abscissa for the positive (red) versus the negative diagnostics (blue). We observe that a strong change in the value of the indicator between positive and negative diagnosis is located in the space value of parameters as the frontier between the trajectory Dominance-Disorder-Crisis shown in table 3. We observe again the various areas observed in the table 3, especially regarding the sign (always posi-δ / σ 0,01 0,03 0,05 0,07 tive or negative, or positive as well as negative and the level of agreement, weaker for low values of σ if δ is large enough. This is then relevant to understand how two agents became disagreeing on their perceived hierarchy. That can be understood from the shape the influence function pij. Fig. 5 reminds how it is for various values of σ. We observe for low values of σ (0.01, 0.05) that the weight becomes very quickly (ie for a small distance) 0 or 1. Then, when δ is close or higher than the distance making the weight close to or equal to 0 or 1, this means that an agent is susceptible to consider her peer from influential to not influential (or almost) in just one meeting and just due to the noise varying from -δ to + δ. Since an agent became not influential (or almost) for another one, she is not listened by her anymore (or almost). Then, it cannot change its image in the other's mind even if it gains a very high reputation, higher than one of the agent which is not able to listen to it. In such a situation, these both agents think they are better than the other. We call the agents who are not anymore able to consider the opinion of a peer an agent blind to this peer.

Considering a it is possible to compute the smallest difference d between the selfopinion an agent and its highest opinion for one of its peer (a ii -a ij ) s for which the corresponding influence is a value  which is small enough for neglecting the possible opinion changes. Derived from the influence function, the equation is:

( ) Fig. 6. Difference (a ii -a ij ) on ordinate between peer and the self in terms of opinion which implies that an agent are not influenced by others for various σ (abscissa) and =0.01.

We observe comparing the fig. 6 to the table 3 that the result is close to define the frontier in the parameter space between the trajectory Dominance-Disorder-Crisis and the other trajectories, if we consider that  is the typical distance between aii and the highest aij. This gives us some information about the frontier between negative and positive patterns.

For the parameters implying numerous disagreements on perceived hierarchies, the population tends to become negative and to show a dominance pattern. In the worst case, when σ is very very small for large values of δ, a significant number of agents consider themselves as superior to all the others: that is the case in the disorder pattern. In case of low disagreement, the observed patterns become positive and have the characteristics of the hierarchy.

Discussion -conclusion

In this paper, we study a simplified version of the Leviathan model, without the processes of vanity and gossiping, keeping only the direct opinion propagation. Like in the complete Leviathan model, we observe patterns representing social orders but some of them are different as well as some new identified properties. This is very surprising such a richness of social orders emerge of the simple fact that the influence function is asymmetric. This is for example the case of two different types of leadership depending if leaders agree on their respective position on not. Overall we diagnosed several patterns organized in trajectories: dominance in which one or two leaders have a low opinion about all the other agents who have negative opinion about each other except about the leaders ; it alternates during a simulation with a crisis pattern in which every agent has a negative opinion about all others, including itself. Disorder is a particular pattern in which the agents have different perceived hierarchies. During simulations several regular sequences of patterns appear. The main ones are: dominance-disorder-crisis, dominance-hierarchy, and hierarchy. Moreover these patterns/ sequences exhibit different average sign of opinions: most of them, except crisis can be of both signs but while the hierarchy is more often positive, dominance is more often negative. This work is a base for developing a new insight onto some behaviors of the Leviathan model by comparing the patterns emerging or not from the processes taking place in the model (ie opinion influence, vanity and gossip).

The patterns of the model can be discussed in light of some sociopsychological researches.

The charismatic leaders at the beginning in the model are the individuals who are viewed as positive by every other. Similarly, the charismatic leadership [START_REF] Van Knippenberg | Leadership, self, and identity: A review and research agenda[END_REF] in the socio-psychological literature is defined as the one who benefits from a high esteem of the larger number of the others. For these same authors, the leadership derives its effectiveness from its influence on follower self-concept which is in turn a moderator of the leadership effectiveness. Identically, for [START_REF] Uhl-Bien | Relational Leadership Theory: Exploring the social processes of leadership and organizing[END_REF] and [START_REF] Hogg | A Social Identity Theory of Leadership[END_REF], "Leadership is a relational term. It identifies a relationship in which some people are able to persuade others to adopt new values, attitudes and goals …". We have seen in the model that overall leaders have a greater influence and tend to determine the value of everyone. However the criteria to define a leader, as well as the process of their emergence, are not so clear. Our modelling study has shown that in some cases leaders have the same perceived hierarchies whereas in other cases their perceived hierarchies are different. So what is more important: the popularity and the capacity to be open to others; or on the contrary, the stubbornness and strong resistance to influence? These results can feed the debate in "leadership" research.

The agents tend to have positive opinions on average when the influence function is smooth (σ large), meaning that the differences of influence according to the perceived hierarchy are small, for a not too large noise (δ). For a sharp influence function and a large noise, agents tend to put themselves high in their perceived hierarchy, and for extreme values, the highest. This is due to the asymmetrical property of the influence function and does not require vanity. This echoes the self-enhancement biases identified long ago in social psychology. [START_REF] Hoorens | Self-enhancement and superiority biases in social comparison[END_REF] particularly stresses the "illusory of superiority" : when subjects estimate their relative position on a number of attributes, they typically report that they possess positive characteristics to a higher, and negative characteristics to a lower, degree than average or most others. This bias is often presented as an inner characteristic of the individual. The model suggests that it is socially built from noisy interactions between agents with strong perceived hierarchies. This explanation deserves some proper experiments to define its relevance.

Fig. 1 .Fig. 2 .Fig. 3 .

 123 Fig. 1. Dominance. For various (δ;σ) couples of value given below the graph and from left to right: Crisis in which no agent has any positive opinion; Negative dominance in which leaders agree; Negative dominance with disagreeing leaders about their respective leadership; Positive dominance with agreeing leaders. For low values of δ and σ, periods of crisis alternate with periods of dominance, even if less frequent. For larger values of values of δ and σ, crisis does not appear anymore and the level of agreement is lower due to the noise. N=20, ρ=0.8.

  if (average opinion < 0) { if (average max-min distance > 2δ) pattern = disorder else { if (average opinion >= -0.5) { if (nb of positive reputation = 0) pattern = crisis else pattern = dominance } } else { if (average max-min distance > 2δ) pattern = disorder else { if ((max opinion -min opinion)> 1) pattern hierarchy else dominance } }

  -DH+/DH+-DH+/DH+-DH+/DH+-DH+/DH+-

Fig. 4 .Fig. 5 .

 45 Fig. 4. Value of the average agreement rate order (size of the circle) for various δ (ordinate) and σ (abscissa) and for globally negative patterns (blue) or positive patterns (pink)

Table 1 .

 1 The colours of the patterns are defined by the sign of the average opinion of the population (blue for negative; red for positive). Quantities are averages over all times and replicas and parameter values for which the diagnosis of pattern and the related relation type between leaders has been identified as described in the table.

	Pattern	Relation	Average	Average	Average num-	Fre-
		between	number of	agreement	ber of agents	quency
		leaders	positive repu-	rate on	thinking being
			tations	order	the best
	Crisis	-	0,0	0,62	1,3	1,77%
	Dominance A	2,2	0,63	1,3 10,73%
		D	1,4	0,60	1,3	4,48%
	Hierarchy	A	8,6	0,85	1,2	5,37%
		D	1,0	0,84	1,1	0,05%
	Disorder	A	2,5	0,72	1,2	2,40%
		D	7,9	0,66	6,6	7,65%
	Dominance A	28,8	0,93	1,0 14,23%
	Hierarchy	D	33,0	0,93	1,1 51,78%
	Disorder	A	24,2	0,47	23,2	0,03%
		D	20,8	0,55	20,4	1,52%

Author-produced version of the paper presented at Social Simulation Conference 2015, Sept 14-18, Groningen, NLD